Kann die Eingabe in eine Turingmaschine unendlich lang sein?

26

Berücksichtigt man nur das Alphabet , stammen die Zeichenfolgen, die als Eingabe für die Turing-Maschinen verwendet werden können, aus der Menge . Aber macht es Sinn, dass die Eingabe eine unendliche Binärzeichenfolge ist? Wenn beispielsweise eine Turing-Maschine alle Zeichenfolgen akzeptiert, die mit einer 0 beginnen, gehört eine binäre Zeichenfolge mit unendlichen Nullen ebenfalls zu der von der Turing-Maschine akzeptierten Sprache?Σ={0,1}Σ

Schärpen
quelle

Antworten:

21

Es ist kein Problem, eine Turing-Maschine auf einem Band auszuführen, das mit einer unendlichen Zeichenfolge initialisiert wurde, obwohl dies normalerweise nicht berücksichtigt wird. Wir brauchen jedoch immer noch die Maschine, um in endlicher Zeit zu enden. Es gibt auch Vorstellungen von Unendlichkeitsberechnungen, die hier angebracht sein können.

Yuval Filmus
quelle
4
Das Beenden der Berechnungen in endlicher Zeit, während die Eingabe unendlich ist, scheint eine schwierige Herausforderung zu sein.
Mast
5
@Mast Nicht unbedingt. Sie können es sich einfach nicht leisten, die gesamte Eingabe zu lesen.
Yuval Filmus
1
@JulesMazur Das Schlüsselwort ist hypercomputation .
Yuval Filmus
3
@JulesMazur Sie benötigen nicht unbedingt eine Hyperberechnung. Das Programm kann einfach weiter auf ein Ausgabeband schreiben, und das Ergebnis konvergiert wie bei einer Turingmaschine vom Typ II zu einer unendlichen Zeichenfolge.
Jkabrg
1
Ich denke, Sie geraten in Schwierigkeiten, wenn Sie unendliche Zeichenfolgen als Eingabe zulassen. Insbesondere der Satz von Eingaben ist nicht mehr zählbar, was mehrere Beweise durchbricht.
Taemyr
17

Das ist eines der Merkmale von Turingmaschinen des Typs 2 . Sie dienen unter anderem dazu, die Berechenbarkeit von Funktionen zwischen reellen Zahlen zu analysieren. Noch interessanter ist, dass sie verwendet werden, um die Berechenbarkeit von Operatoren wie der Integration zu analysieren.

Coole Tatsache: Eine exakte numerische Integration ist berechenbar.

jkabrg
quelle
5

Zur Beantwortung der Frage "Macht es Sinn?" Kann dies sogar nützlich sein, wenn Sie Turing-Maschinen in Betracht ziehen, die in endlicher Zeit laufen.

Insbesondere ist dies eine sehr nützliche Art, sich Turing-Maschinen ohne Präfix vorzustellen . Hierbei handelt es sich um Maschinen, bei denen die Eingabe von Stopps keine Präfixe enthält. Das heißt, keine Eingabe, die zum Anhalten des Computers führt, ist das Präfix einer anderen. Diese haben die gleiche Leistung wie normale Turing-Maschinen, jedoch nur, wenn wir der Turing-Maschine erlauben, ihre eigenen Halteeingaben zu bestimmen: dh. Der Benutzer hat keine Ahnung, bei welchen Eingaben die Maschine anhält (und dies ist eine unentscheidbare Eigenschaft).

Eine Möglichkeit, dies zu sehen, ist eine normale Turing-Maschine mit einem unendlichen Einweg-Eingabeband mit einem Bandkopf, der sich nicht zurückbewegen kann. Der Benutzer füllt das Band mit Bits und führt die Maschine aus. Dies ist per Definition eine präfixfreie Turingmaschine. Wenn die Maschine anhält, muss sie nur eine begrenzte Anzahl von Bits gelesen haben, und kein Präfix dieses Teils des Bandes kann ein Programm sein, oder die Maschine hätte stattdessen dort angehalten.

Dies ist ein guter Weg, um über berechenbare Wahrscheinlichkeitsverteilungen zu sprechen: Der Benutzer füllt das Band mit zufälligen Bits (der Zufallsquelle der Maschine) und die Maschine spuckt eine zufällige Bitfolge aus. Die Menge all dieser Turing-Maschinen entspricht der Menge der berechenbaren Verteilungen (insbesondere der unteren halbberechenbaren Halbmaße).

Der Vorteil der unendlichen Eingabe besteht darin, dass wir nicht angeben müssen, was die Maschine tut, wenn wir ihr das Präfix eines Stoppprogramms geben, d. H. Die Maschine versucht, über das Ende der von uns eingegebenen Eingabe hinaus zu lesen.

Peter
quelle
2

Selbst wenn Sie kein solches Band haben, können Sie eine andere Turing-Maschine verwenden, um es zu produzieren.

Eine Turing-Maschine hat Zugriff auf das leere, aber unendliche Datenband (oder einige Quellen besagen, dass in der Maschine nur eine kleine Bandfabrik eingebaut ist). So kann es mit einem programmierbaren Datenmuster initialisiert werden, und das Band kann dann als Eingang einer anderen Turing-Maschine verwendet werden.

Wenn Ihr Inhalt so ist, dass kein Algorithmus zu seiner Erstellung definiert werden kann, kann dieser Inhalt natürlich nicht von Turing machine erstellt werden.

h22
quelle
6
Ich bin nicht sicher, wie dies die Frage beantwortet. In jedem Fall können nicht alle unendlichen Folgen von Turing-Maschinen erzeugt werden, da es unzählige unendliche Folgen über einem Alphabet mit mindestens zwei Symbolen gibt, während es nur unzählige Turing-Maschinen und unzählige endliche Eingaben gibt, mit denen sie gesät werden können.
David Richerby
2

In einigen Fällen kann eine unendliche Eingabe in Betracht gezogen und auf die Aktion einer "normalen" Turing-Maschine reduziert werden. Betrachten Sie beispielsweise ein sich unendlich wiederholendes endliches Muster, das in der Eingabe angegeben ist. Es kann eine Turing-Maschine erstellt werden, die festhält, wie viel dieses unendlichen Musters durch die aktuellen Aktionen des Bandkopfs unter Verwendung einer begrenzten Menge an Speicher / Bandspeicher geändert wurde. Mit anderen Worten, es simuliert "äquivalent" ein unendliches Größenmuster auf dem Band.

Ein anderer Fall, in dem "unendliche Eingabe" in Betracht gezogen wurde, ist die Analyse der Turing-Äquivalenz / Vollständigkeit von zellulären Automaten. In einem komplexen Beweis führte Cook ein Konzept ein, das nun von einigen als "schwache Turing-Äquivalenz" bezeichnet wird, wenn CA 110- Regeloperationen in Turing-Maschinenoperationen konvertiert werden, die auf einem unendlich festgelegten Anfangsband beginnen, jedoch (sich wiederholende) Muster endlicher Größe aufweisen.

vzn
quelle
1
Die Begriffe "unendliche Eingabe" und "endliche Codierung eines unendlichen Objekts" sind klar voneinander getrennt und elementar (jede unendliche reguläre Sprache mit minimalem DFA ist ein Beispiel). Sie sollten hier nicht verwechselt werden.
Raphael
2
ja DFAs können für die beschriebene Codierung verwendet werden. Wie skizziert, ist ein Band mit einer endlichen Kodierung einer Zeichenkette unendlicher Länge (über wiederholte endliche Muster) in der Fähigkeit zu einem Band mit nur endlichen Zeichenketten unterschiedlich / ähnlich.
vzn
1

In formalen Sprachen ist eine Zeichenfolge per Definition eine endliche Folge von Symbolen. Eine klassische Turing-Maschine hat ein Endlosband mit einer endlichen Eingabesaite. Obwohl es keine Begrenzung für die Länge der Eingabe gibt, kann sie nicht unendlich sein.

Allerdings gibt es viele alternative Maschinen, die ähnlich wie ein TM funktionieren, jedoch mit unendlichen Eingabesequenzen.

Ob eine Eingabe von unendlicher Länge sinnvoll ist, hängt vom Verwendungszweck ab. Streng genommen im Kontext von Turing-Maschinen ergibt es keinen Sinn (da es nicht möglich ist), aber im Kontext von Turing-ähnlichen Maschinen ergibt es Sinn und es hat viele Anwendungen.

jeder
quelle
4
Es ist durchaus möglich, unendlich viele Zeichenfolgen zu haben. In der Tat gibt es einen ganzen Zweig der Automatentheorie, der sich genau mit dieser Situation befasst. Und da die einzige Änderung an der Definition von Turing-Maschinen erforderlich ist, damit sie mit unendlichen Eingaben umgehen können, besteht die Löschung der Bedingung, dass die Eingabe endlich sein muss, und ich bin nicht der Meinung, dass es "keinen Sinn" macht, über Turing-Maschinen und zu sprechen unendliche Saiten.
David Richerby
1
@DavidRicherby: wir scheinen uns einig zu sein. Zögern Sie nicht, mir mitzuteilen, wie ich den letzten Absatz umformulieren kann, um klarer zu machen, dass es nur im Zusammenhang mit ursprünglichen, klassischen, unverfälschten Turing-Maschinen (bei denen die Eingaben per Definition endlich sind) keinen Sinn ergibt Sprechen Sie über unendlich lange Eingabe. Sobald wir die Bedingung löschen, handelt es sich nicht mehr ausschließlich um ein TM, sondern (wie ich es nannte) um eine Turing-ähnliche Maschine.
alle
1
Ich bin nicht einverstanden, dass das Gerät keine Turing-Maschine mehr ist, nur weil Sie es mit unendlichen Dingen auf dem Band starten. Die Maschine ist immer noch dieselbe Maschine; Sie haben gerade die Anfangsbedingungen geändert. Die Definitionen, wie sich Turing-Maschinen auf Sprachen endlicher Saiten beziehen (z. B. entscheidbare oder halbentscheidbare Sprachen), beziehen sich auf endliche Eingaben, aber das bedeutet nicht, dass die Maschine dies benötigt. Ebenso würde Ihr Computer nicht aufhören, ein Computer zu sein, wenn Sie einen unendlichen Stapel von CD-ROMs daneben legen.
David Richerby
1
@DavidRicherby Nun, technisch gesehen ist eine Turing-Maschine eine Maschine, die endliche Eingaben benötigt. Wenn Sie diese Einschränkung in der Definition ändern, definieren Sie etwas anderes. Die Idee hinter dem Rechnen ist in gewissem Sinne immer noch dieselbe, aber wie drückt man Komplexität jetzt aus? Sehr unterschiedliche Themen.
Raphael