Diskussion:Terminiertheit

aus Wikipedia, der freien Enzyklopädie
Letzter Kommentar: vor 13 Jahren von Mussklprozz in Abschnitt Abschnitt Mechanische Terminierungsbeweise
Zur Navigation springen Zur Suche springen

Terminiertheit der Ackermannfunktion

[Quelltext bearbeiten]

A(0, n) = n + 1

A(m+1, 0) = A(m, 1)

A(m+1, n+1) = A(m, A(m+1, n))

"Abstiegfunktion"

[Quelltext bearbeiten]

Ordnung über N x N mit (0,0) < (0,1) < (0,2) < ... < (1,0) < (1,1) < ...

Der "Abstieg" wird induktiv sowohl über m (äußere Induktion) als auch über n bei festem m gezeigt (innere Induktion).

Vielleicht kann ich das bei Gelegenheit mal formal ausdrücken. --Calgath 21:32, 12. Dez 2005 (CET)

weitere ähnliche Definitionen

[Quelltext bearbeiten]

Habe den Artikel folgendermaßen überarbeitet:

  1. Definition und Zusammenhang der Begriffe terminiert für Eingabe und terminiert überall.
  2. Die Ackermannfunktion gefällt mir nicht so recht als Beispiel, denn sie ist kaum von praktischem Interesse. Ich hätte hier lieber ein praktisches Beispiel. Wie wäre es mit dem Euklidischen Algorithmus?
  3. Den Bezug zur Entscheidbarkeit habe ich gelöscht, denn er gehört nach meiner Meinung nicht hierher.
  4. Zu Terminierungsbeweisen sollte es einen eigenen Artikel geben, den ich gerne schreiben werde.
  5. Ich habe auch die Querverweise zum Halteproblem präzisiert und auf das Gleichmäßige Halteproblem (englisch: uniform halting problem) verwiesen. Gibt es zum Gleichmäßigen Halteproblem schon irgendwas in wikipedia?--AlfonsGeser 23:32, 9. Mai 2008 (CEST)Beantworten

"Gleichmäßiges Halteproblem"

[Quelltext bearbeiten]

Von dem Begriff habe ich so noch nie gehört. Und ich sehe keinen Grund den Link so zu lassen. Es kann auch auf's Haltproblem gelenkt werden. Das aus dem Problempaar (Programm, eine Eingabe) = unlöslich, folgt, dass es (erst Recht!) unmöglich ist, etwas auf alle Eingaben zu testen, kann man doch leicht einsehen bzw. leicht beweisen und außer dass man das mal benennt kenne ich also keinen eigenständigen Begriff hierfür. Weil ich mutig bin ändere ich das also -erstmal- und wenn jemand mehr weiß als ich, freue ich mich was zu lernen. Grüße --WissensDürster 12:43, 18. Feb. 2009 (CET)Beantworten

PS: Google findet auch absolut nichts zu dem Begriffpaar, nur als Legitimation 0:)

Hallo mutiger WissensDürster. Hast Du den vorigen Disk-Beitrag gelesen? :-) --Steevie schimpfe hier :-) 20:54, 18. Feb. 2009 (CET)Beantworten

Hm leider nicht. Aber danke - wie peinlich. Das ändert aber nichts daran, dass en.wiki das "uniform halting problem" auch nicht behandelt bzw. es dazu nur ein paar englische Quellen gibt, die alle nach Forschung aussehen. Erst Recht ist also fraglich, ob dann die "deutsche Übersetzung" überhaupt ein Fachterminus ist?! Sinnvoll erscheint hier also, weil man im dt. nichts findet, zu erwähnen, dass ein derartiger Sachverhalt im Englischen "uniform halting problem" genannt wird - und es ist zu unwahrscheinlich, dass irgendein Wikipedianer dieses Problem gerade hier lösen könnte, deshalb muss der rote Link auch nicht sein. Grüße --WissensDürster 13:23, 19. Feb. 2009 (CET)Beantworten

Ich wollte Dich bloß auf den Beitrag von AlfonsGeser hinweisen, nicht Deinen Edit kritisieren. :-) Das mit dem Fachterminus ist wirklich schwierig, (Prof.) Alfons Geser hatte ihn zumindest verwandt. Wegen des roten Links würde ich vielmehr eine Weiterleitung auf Halteproblem anlegen oder den, meiner Meinung nach jetzt irreführenden, Link ganz entfernen, denn Halteproblem ist kurz zuvor bereits verlinkt. Viele Grüße, --Steevie schimpfe hier :-) 14:06, 19. Feb. 2009 (CET)Beantworten

Ja, der Link war natürlich auch nicht hilfreich. Auch eine Weiterleitung wäre fehl am Platz, da in Halteproblem, dass Lemma ja nicht ein Mal benannt wird. Also habe ich es "fett" gekennzeichnet, soll heißen, es ist eine begriffliche Wortgruppe, aber nicht weiter konkretisiert. Ich denke das geht so. Grüße --WissensDürster 14:31, 19. Feb. 2009 (CET)Beantworten

Du hättest aber gerne für die Nennung in Halteproblem sorgen dürfen. :-) --Steevie schimpfe hier :-) 14:45, 19. Feb. 2009 (CET) PS: A ... distinction exists between the halting problem and the uniform halting problem for Turing machines....Beantworten

Fragwürdiges

[Quelltext bearbeiten]

Terminierung und Terminiertheit sind etwas anderes. Terminierung bezeichnet den Abschluss einer einzelnen Berechnung, Terminiertheit bezeichnet eine allgemeine Eigenschaft eines Allgorithmus.

„Dass ein Algorithmus für eine Eingabe a unendlich lange rechnet, also für a nicht terminiert, weist man dadurch nach, dass man die unendliche Berechnung für a angibt.“ – Das ist Quark, denn aus der Existenz einer unendlichen Berechnung folgt nicht die Nicht-Existenz einer endlichen Berechnung.

Die Ackermannfunktion bietet keinen zusätzlichen Erklärungswert und bläht nur den Artikel auf. Dass die Dauer der Berechnung mit der Länge der Eingabe steigt, ist der Normalfall.

--Mussklprozz 12:29, 12. Jul. 2011 (CEST)Beantworten

Abschnitt Mechanische Terminierungsbeweise

[Quelltext bearbeiten]

Der Abschnitt wurde aus dem Artikel Halteproblem am 12. Juli 2011 13:00 CEST übernommen ([1]). Zur Versionsgeschichte von Halteproblem bis Juli 2011 siehe [2]. --Mussklprozz 13:06, 12. Jul. 2011 (CEST)Beantworten