Diskussion:Terminiertheit

Terminiertheit der Ackermannfunktion

Definition

A(0, n) = n + 1

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

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

"Abstiegfunktion"

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

Ansatz

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

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)

"Gleichmäßiges Halteproblem"

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)

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)

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)

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)

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)

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....

Fragwürdiges

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)

Abschnitt Mechanische Terminierungsbeweise

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)