Nehmen Turingmaschinen irgendwann etwas Unendliches an?

In einer vorherigen Frage Was genau ist ein Algorithmus? Ich fragte, ob ein "Algorithmus", der den Wert einer Funktion basierend auf einem Array vorberechneter Werte zurückgibt, ein Algorithmus sei.

Eine der Antworten, die meine Aufmerksamkeit auf sich zogen, war diese:

Das faktorielle Beispiel befasst sich mit einem anderen Berechnungsmodell, das als ungleichmäßige Berechnung bezeichnet wird. Eine Turingmaschine ist ein Beispiel für ein einheitliches Rechenmodell: Sie hat eine einzige, endliche Beschreibung und funktioniert für Eingaben beliebig großer Größe. Mit anderen Worten, es gibt ein TM, das das Problem für alle Eingangsgrößen löst.

Nun könnten wir stattdessen die Berechnung wie folgt betrachten: Für jede Eingabegröße gibt es ein TM (oder ein anderes Rechengerät), das das Problem löst. Dies ist eine ganz andere Frage. Beachten Sie, dass ein einzelnes TM nicht die Fakultät jeder einzelnen Ganzzahl speichern kann, da das TM eine endliche Beschreibung hat. Wir können jedoch ein TM (oder ein Programm in C) erstellen, das die Fakultäten aller Zahlen unter 1000 speichert. Dann können wir ein Programm erstellen, das die Fakultäten aller Zahlen zwischen 1000 und 10000 speichert. Und so weiter.

Nimmt nicht jedes TM tatsächlich einen Weg an, mit Unendlichkeit umzugehen? Ich meine, sogar ein TM mit einer endlichen Beschreibung, die die Fakultät einer beliebigen Zahl N durch den Algorithmus berechnet

 int fact(int n) 
 { 
 int r = 1; 
 for(int i=2;i<=n;i++) 
 r = r*i; 
 return r; 
 } 

enthält die Annahme, dass ein TM die "Hardware" hat, um Zahlen beliebiger Größe durch den "<=" - Komparator zu vergleichen, und ADDER, um i bis zu einer beliebigen Zahl zu erhöhen, und darüber hinaus die Fähigkeit, Zahlen beliebiger Größe darzustellen.

Vermisse ich etwas Warum ist der Ansatz, den ich in meiner anderen Frage vorgestellt habe, in Bezug auf die Unendlichkeit weniger machbar als dieser?

<=<=$Q$$\Sigma$

<=$|Q|$$|\Sigma|$

Turingmaschinen "beschäftigen sich nicht wirklich mit Unendlichkeit": Sie befassen sich mit unbegrenzten endlichen Dingen, zumindest in ihrer Standarddefinition. Die Eingabe ist eine endliche Zeichenfolge, und nach einer endlichen Anzahl von Schritten hat die Maschine nur eine endliche Anzahl von Bandzellen untersucht oder in diese geschrieben. Es gibt keine Begrenzung für die Größe der Eingabe oder die Anzahl der Berechnungsschritte, aber die Eingabe ist endlich und nach einer endlichen Anzahl von Schritten wurde nur eine endliche Menge an Ausgabe erzeugt.

Ich denke, der wichtige Unterschied besteht darin, dass die Beschreibung der Turing-Maschine endlich ist, ebenso wie die Eingabe in die Maschine, während das Band, das sie als Speicher verwendet, unendlich ist. Das TM ist eine meist endliche Maschine, die ein endliches Band verwendet. Stellen Sie sich das Band vor, das aus Zellen besteht, wobei jede Zelle einen einzelnen Wert enthalten kann. Die Eingabe in das TM wird auf das Band geschrieben.

Die Beschreibung eines TM ist eine endliche Menge von Tupeln <current state, input, output, move, next state>.

Bei jedem Schritt wird das zu erledigende Element gefunden, indem der aktuelle Status und die Eingabe abgeglichen werden. ZB sind wir im Zustand 0 und lesen eine 1, also finden wir das Tupel, das beginnt, <0, 1, ...>dann schreiben wir einen neuen Wert in die aktuelle Zelle, bewegen uns nach links oder rechts (ich denke, die klassische Definition erlaubt es auch, in derselben Zelle zu bleiben auch) und dann in einen neuen Zustand wechseln.

Für Ihr Beispiel benötigen Sie entweder eine unendlich große Beschreibung des TM (eine unendliche Anzahl von <current state, input, output, move, next state>Tupeln) oder fügen die Suchinformationen in die Eingabe für das TM ein. Ich glaube, die Eingabe in ein TM ist als endlich definiert. Das ist wahrscheinlich nichts, was man mit einer klassisch definierten Turing-Maschine machen könnte.

Im Gegensatz dazu kann das Fibonacci-Beispiel binär mit einer endlichen Anzahl von Tupeln berechnet werden, um das TM zu beschreiben, und hat eine endliche Eingabe.

Kurz gesagt : Turing Machine kann (endlich spezifizierte) unendliche Berechnungen an (endlich spezifizierten) unendlichen Daten durchführen und (endlich spezifizierte) unendliche Ergebnisse erzeugen. Die Grundidee ist, dass diese Unendlichkeiten als die Grenze endlicher Entitäten definiert werden können, die auf mathematisch angemessene Weise definiert werden. Dies ist die Grundlage der mathematischen Berechnungssemantik. Wenn Sie eher Programme als Turing-Maschinen betrachten, können diese Programme auch (endlich spezifizierte) unendliche Datenstrukturen enthalten. Der Fall einer tabellarischen Funktion factals möglicher Algorithmus wird am Ende als Programm oder als TM-Modell mit einem Hinweis auf die Beziehung zur verzögerten Bewertung unendlicher Objekte analysiert.

Mit vielen weiteren Details

In Bezug auf Ihre letzte Frage berechnet ein TM nicht aus beliebigen Zahlen, sondern aus der symbolischen Darstellung dieser Zahlen als willkürlich (unbegrenzt) lange Zeichenfolgen, die sie darstellen. Modulo richtige Codierung, ist es richtig, dass sie mit solchen Zahlen durch diese Darstellungen vergleichen oder rechnen können.

Die ursprüngliche Frage betrifft jedoch die Rolle der Unendlichkeit in Turingmaschinen im Allgemeinen.

Eine häufige Antwort auf diese Frage ist, dass Turing-Maschinen niemals mit Unendlichkeit umgehen. Sie sind endlich definiert, und was auch immer sie berechnen, wird in endlicher Zeit auf einem endlichen Teil des Bandes berechnet (daher würde ein endliches Band, das größer ist, ausreichen). Was wahr ist, ist, dass der zeitliche Platzbedarf des TM unbegrenzt ist, was nicht dasselbe ist wie unendlich.

Daher könnte jede Antwort, die von einem TM berechnet wird, auch von einem Finite-State-Automaten (FSA) berechnet werden, was "bis zu einem gewissen Grad" eine Möglichkeit ist, die Tabellierung zu betrachten. Die Schwierigkeit besteht darin, dass einige Eingabegrößen (es kommt fast immer dazu, wenn nur die Eingabe gelesen wird) die Größe des Automaten überschreiten. Aber dann können wir einfach einen größeren verwenden. Wenn wir also die unbegrenzte Eingabegröße berücksichtigen möchten, benötigen wir eine unendliche Folge von FSA, die die Berechnung durchführen kann. Tatsächlich benötigen wir möglicherweise eine Finite-State-Maschine, die etwas komplexer ist als die herkömmliche FSA, da möglicherweise eine Ausgabe berechnet werden muss (anstelle einer Ja-Nein-Antwort), aber ein Finite-State-Wandler sollte dies wahrscheinlich tun.

Wenn wir uns also ein Problem ansehen, das eine unendliche Menge von Instanzen hat, wie zum Beispiel die Berechnung einer GCD oder einfach die Verwendung von Arithmetik für ganze Zahlen beliebiger Größe, sehen wir, dass die Unendlichkeit durch die Hintertür auf uns zurückkommt, als diese Unendlichkeit Satz von FSA.

$\pi$

Andererseits können wir dies durch eine unendliche Folge endlicher Berechnungen durch endliche Maschinen ersetzen. Aber betrügen wir?

Aus physikalischer Sicht ist das das Beste, was wir tun können. Wir wissen nur, wie man endliche Maschinen baut, zumindest nach dem aktuellen Stand der Physik, von dem in naher Zukunft nicht allzu viel erwartet wird.

Aber wie können wir diese Unendlichkeiten aus mathematischer Sicht konsistent und nachvollziehbar behandeln?

Wenn Sie eine unendliche Menge von FSA betrachten, die zusammenarbeiten kann, um eine unendliche Menge von Antworten zu berechnen, können Sie dies nicht willkürlich tun. Sie benötigen einige Sicherheitsvorkehrungen, um sicherzustellen, dass das, was Sie tun, Sinn macht. Es ist bekannt, dass Sie jede Menge trivial mit einer unendlichen Vereinigung regulärer Mengen erstellen können, tatsächlich mit einer unendlichen Vereinigung von Singleton-Mengen. Wenn Sie also beliebige unendliche Vereinigungen von Automaten ohne Einschränkung betrachten, werden Sie nirgendwohin führen. Sie berücksichtigen sogar in demselben Satz Automaten, die Ihnen inkonsistente Antworten geben.

Was Sie wirklich wollen, ist einen Begriff der Konsistenz zu definieren. Dies erfordert jedoch einige Vorsichtsmaßnahmen. Nehmen wir an, Sie verwenden eine unendliche Folge von Automaten, um ein TM zu simulieren, das mit Ja oder Nein antwortet oder nicht anhält. Das Problem ist, dass eine FSA immer mit einer Antwort wie Ja oder Nein anhält. Wenn Sie jedoch eine FSA verwenden, deren Größe für die ausgewählte Eingabe nicht groß genug ist, worauf sollte sie antworten? Sowohl Ja als auch Nein sind für die Fälle reserviert, in denen die FSA die TM-Berechnung tatsächlich beendet hat, und die Verwendung einer dieser Antworten mit einer unvollendeten Berechnung würde nur zu Verwirrung führen. Was Sie wollen, ist eine Antwort, die sagt: " Entschuldigung, ich bin zu klein und ich kann es nicht sagen. Bitte versuchen Sie es mit einem größeren Mann in der Familie. " Mit anderen Worten, Sie möchten eine Antwort wie Überlauf oder wissen es nicht$\bot$

Sie benötigen also Automaten mit drei Arten von Zuständen: Akzeptieren, Nichtakzeptieren und Undefiniert. Ein undefinierter Zustand kann als ein Zustand angesehen werden, der für einen fehlenden Teil des Automaten steht, der die Berechnung zum Stoppen zwingt. Wenn die Berechnung angehalten wird, erhalten Sie abhängig vom Status, in dem sie angehalten wird, die Antwort Ja , Nein oder Undefiniert .

Jetzt sehen Sie, dass Sie unendlich viele Folgen von Automaten wollen, die konsistent sind . Sowohl Ja als auch Nein stimmen mit undefiniert überein , aber Ja stimmt nicht mit Nein überein . Dann sind zwei Automaten konsistent, wenn sie konsistente Antworten auf dieselbe Eingabe geben.

$\pi$$3.14\bot\bot\bot\bot...$$3.1415\bot\bot\bot\bot...$$\bot.\bot5159\bot\bot\bot\bot...$$3.1416\bot\bot\bot\bot...$$3.1416\bot\bot\bot\bot...$$\pi$

Ich werde diese theoretischen Aspekte nicht weiterentwickeln, was auf der Basis von Turing-Maschinen etwas umständlich ist. Der Punkt ist, dass diese Konzepte zu der Idee führen, dass Berechnungsdomänen (ob Daten oder Maschinen) mathematische Strukturen wie Gitter bilden, in denen unendliche Objekte angemessen definiert werden können als die Grenzen von unendlich ansteigenden (dh besser und besser definierten) Sequenzen von endliche Objekte. Das Definieren der unendlichen Sequenzen erfordert etwas mehr Apparat und einen Begriff der Kontinuität. Dies ist im Grunde das, worum es in Dana Scotts Theorie der Semantik geht, und sie gibt eine etwas andere Sicht auf die Konzepte der Berechenbarkeit.

Dann können Turing-Maschinen oder andere formale Geräte, die "unendliche Berechnungen" durchführen können, als Grenzen von Sequenzen endlicher Approximationen der Maschinen definiert werden, die immer besser definiert werden. Gleiches gilt für alle Daten, mit denen die Maschinen rechnen, egal ob Eingabe oder Ausgabe.

Das einfachste Dokument, das ich jemals darüber gelesen habe, ist ein handgeschriebener Satz von Vorlesungsunterlagen von Dana Scott, die oft als Amsterdamer Vorlesungsunterlagen bezeichnet werden. Aber ich konnte es nicht im Web finden. Jeder Hinweis auf eine Kopie (auch unvollständig, da ich einen Teil davon habe) wäre willkommen. Sie können sich aber auch andere frühe Veröffentlichungen von Scott ansehen, z. B. Überblick über eine mathematische Berechnungstheorie .

Zurück zum ersten Beispiel der Frage

Diese Approximationskonzepte gelten sowohl für Daten als auch für Programme. Die Funktion factwird rekursiv definiert, was bedeutet, dass es der am wenigsten feste Punkt einer Funktion ist, der verwendet werden kann, um eine Sequenz zu berechnen, die die endliche Approximation von konvergiert fact. Diese Folge von immer mehr definierten endlichen Funktionen konvergiert zu einer unendlichen Entität, die Sie als Funktion bezeichnen fact.

fact$\bot$

Es ist wahr, dass, wenn Sie das elementare TM-Berechnungsmodell betrachten, ein solches unendliches Array in diesem Formalismus nicht ausgedrückt werden kann. Das bedeutet nicht, dass es keinen Sinn ergeben würde. Eine Turing-Maschine könnte ein zweites Band haben, das mit den tabellarischen Werten einiger Funktionen wie z fact. Es ändert nichts an der Rechenleistung des TM, solange diese Funktion berechenbar ist, dh solange die Tabelle mit einer unendlichen Berechnung eines anderen TM initialisiert werden kann, das alle Argument-Wert-Paare für die relevante Funktion berechnen kann.

In der Praxis können Sie jedoch keine unendliche Berechnung durchführen. Daher ist es der richtige Weg, die Tabelle träge zu berechnen, dh Einträge nur bei Bedarf zu füllen. Genau das geschieht mit dem Auswendiglernen. Dies ist die Antwort, die ich Ihnen mit unterschiedlichen Begründungen auf Ihre vorherige Frage gegeben habe.

Der Kern dieser Antwort ist, dass Turing-Maschinen alles nachahmen können, was wir programmieren können, und wir programmieren Berechnungen an, mit und von unendlichen Objekten.

Dies ist eine zweite Antwort, die sich mehr auf die spezifische gestellte Frage als auf den allgemeinen theoretischen Rahmen konzentriert, der die Antwort rechtfertigt, und der definitiv zur Beantwortung des allgemeineren Titels der Frage benötigt wird. Es ist voll kompatibel mit meinen vorherigen Antworten auf die Fragen des OP. Was genau ist ein Algorithmus? und Nehmen Turingmaschinen irgendwann etwas Unendliches an? , Antworten, in denen ich mehr den theoretischen Kontext entwickelt habe. Dies kann als Beantwortung beider Fragen angesehen werden.

Turing-Maschinen haben die Fähigkeit, mit Unendlichkeit umzugehen , wie alle vollständigen Turing-Rechenmodelle, wenn auch nur mit unzähligen Unendlichkeiten. Unser Problem ist, dass wir nur einen Teil dieser Unendlichkeit beobachten können, aber wir müssen das Ganze berücksichtigen, da der Teil, den wir beobachten können, unbegrenzt ist.

Das andere Problem ist, dass wir uns nur mit endlich spezifizierten Entitäten befassen können. Tatsächlich fällt die gesamte Struktur der Wissenschaft, wie wir sie kennen, zusammen, wenn wir Entitäten betrachten, die nicht endlich spezifiziert sind, da es unmöglich wird, die Konsistenz von Definitionen zu überprüfen und sogar zu wissen, was die Definitionen sind, da wir nur auf einen Teil davon zugreifen können eine endliche Zeit.

Möglicherweise gibt es ein weiteres grundlegendes Problem, das der Tatsache ähnelt, dass der Abschluss unter unendlicher Vereinigung jede gewünschte Menge definiert, es sei denn, Sie können die in einer solchen Vereinigung zulässigen Bedingungen angemessen einschränken. Ich bin mir jedoch nicht sicher, ob ich dieses Problem vollständig verstehe.

Wie gesagt, Turing-Maschinen haben die Fähigkeit, mit Unendlichkeit umzugehen . Ich widerspreche anderen gut bewerteten Antworten einiger Benutzer mit hohen Repräsentanten, die wissen sollten, worüber sie zu einem so elementaren Thema sprechen.

Das Problem ist, dass Turing ein sehr elementares Rechenmodell gewählt hat, um seinen theoretischen Zweck zu erreichen. Je einfacher, desto besser. Für fortgeschrittenere / anspruchsvollere Rechenmodelle ist es so ziemlich die Maschinensprache für die Programmierung: etwas sehr Dunkles, bei dem Sie keines der Konzepte erkennen können, die für die Programmierung auf hoher Ebene sinnvoll sind. Tatsache ist, dass TM wie die Maschinensprache viel mehr nachahmen kann, als sie direkt ausdrücken können.

$23{rd}$ Aber es wird immer noch oft als unendliche Berechnung implementiert, die künstlich gestoppt wird, wenn die richtige Antwort erreicht ist.

Tatsächlich fügen alle Benutzer, die angeben, dass in einem TM alles endlich, aber unbegrenzt ist, sehr sorgfältig hinzu, dass sie Turing-Maschinen in ihrer Standarddefinition berücksichtigen . Das Problem ist, dass die Standarddefinition nur ein Mittel zur Vereinfachung der Theorie ist, aber beim Versuch, Rechenstrukturen zu verstehen, ziemlich irrelevant ist.

Tatsächlich ist das einzige, was bei der Berechnung wichtig ist, dass alles auf berechenbare Weise endlich spezifiziert werden muss, nicht dass es endlich ist .

Wir gehen davon aus, dass eine Turingmaschine ein endliches Objekt sein muss. Das stimmt aber nicht. Sie können ein Modell einer Turing-Maschine mit einem zweiten Band definieren, das schreibgeschützt ist und eine Funktion enthält, die für alle ganzzahligen Werte ohne Begrenzung tabellarisch aufgeführt ist. Das ist unendlich. Sie erhalten jedoch keine zusätzliche Rechenleistung, solange der Inhalt dieses Bandes rechnerisch spezifiziert ist (die Berechenbarkeit impliziert, dass er endlich spezifiziert ist). Das zusätzliche Band könnte durchaus durch eine in das andere eingebettete TM-Maschine ersetzt werden und würde die Antworten liefern, anstatt sie auf dem zusätzlichen Band zu suchen. Von einer höheren Ebene ist der Unterschied nicht sichtbar.

Unter dem Gesichtspunkt der praktischen Realisierung könnten wir eine fact Turing-Maschine haben, die Fakultäten berechnet und auf dem zusätzlichen Band tabelliert, während ein anderes TM die tabellierte Fakultät aus dem zusätzlichen Band verwendet und nur auf das erste TM wartet, wenn in der Tabelle noch einige fehlen Eintrag. Die zweite Maschine geht jedoch davon aus, dass der Inhalt des Bandes letztendlich unendlich ist. Die Tabelliermaschine muss nicht einmal die ganze Zeit arbeiten, sondern muss die Berechnung fortsetzen, wenn Daten aus der Tabelle angefordert werden und dort nicht gefunden werden.

Zurück zur Frage: Der Hauptunterschied zwischen unbegrenzten ganzen Zahlen und der unendlichen Tabelle besteht nur darin, dass ganze Zahlen endlich, unbegrenzt, aber vollständig in endlicher Zeit berechnet sind. Die unendliche Tabelle wird auf unbestimmte Zeit berechnet, ist endlich, wächst aber immer noch bis ins Unendliche. Das ist kein Problem, aber ein Unterschied. Unendliche Objekte sind nur durch endliche Näherungen zugänglich, ... aber sie sind unendlich. Berechenbare irrationale Zahlen sind in diesem Sinne unendliche Objekte, zumindest für ihre Darstellung als Binärzahlen.

Alle Algorithmen werden im Kontext einer mathematischen Theorie definiert. Und eine Tabellensuche zusammen mit einer unendlichen Tabelle ist ein Algorithmus. Es handelt sich jedoch um einen Algorithmus in einer mathematischen Theorie mit einer endlich definierten unendlichen Menge von Axiomen, die die Werte einer Funktion, die sie für jedes ganzzahlige Argument axiomatisiert, ausführlich (und nicht intensiv) spezifizieren. (Siehe meine Antwort auf Ihre vorherige Frage ). Dann ist es immer legitim, dies zu tun, da Sie den Axiomen einer Theorie immer nachweislich wahre Aussagen hinzufügen können.

Usul-Aussagen, wie sie in Ihrer aktuellen Frage wiedergegeben sind, sind meiner Meinung nach falsch (obwohl alles auch eine Frage der Definition ist). Seine Schlussfolgerung in seiner Antwort , dass Sie nicht reproduziert haben, ist, dass die Verwendung einer unendlichen Tabelle nicht als Algorithmus betrachtet werden kann, da sie nur durch ein ungleichmäßiges Berechnungsmodell, durch eine Sammlung verschiedener Maschinen und damit implementiert werden kann Verwendungen " haben keine endliche Beschreibung, die implementiert werden kann, um das" gesamte "Problem für jede Eingabegröße zu lösen$\pi$

Die Art und Weise, wie solche unendlichen Entitäten in der Praxis berechnet werden, erfolgt durch verzögerte Auswertung , Berechnung des jeweils benötigten Teils und Wiederaufnahme der Berechnung für einen Teil des Restes, wenn mehr benötigt wird. Dies ist genau das, was oben vorgeschlagen wurde fact, wenn die Maschine träge Fakultät berechnet, um in einer Tabelle gespeichert zu werden, wenn mehr Daten aus der Tabelle benötigt werden.

In gewisser Weise scheint dies die Behauptung (in DanielVs Antwort ) zu bestätigen, dass der Codespace endlich sein muss, da die verzögerte Bewertung tatsächlich auf einem endlichen Code basiert. Die Berechenbarkeit ist jedoch ein allgegenwärtiges Codierungsspiel, so dass die Unterscheidung von Code und Daten unter anderem in den Augen des Betrachters immer ziemlich wichtig ist. In der Tat machen viele moderne Programmiersprachen keinen großen Unterschied zwischen der intensiven und der erweiterten Spezifikation von Werten, und die Denotational Semantics unterscheidet "2 + 2" nicht wirklich von "4". Semantik ist wirklich das, worüber wir sprechen, wenn wir eine Frage wie " Was ist X ? " Stellen .

Diese Ansicht der Endlichkeit von Code, die auch als statisch angesehen wird, ist ein weiterer Grund, warum eine unendliche Tabelle (als Teil des Codes betrachtet) nicht gleichberechtigt mit unbegrenzten Ganzzahlen betrachtet wird, die als Daten verwendet werden. Dies ist jedoch eine weitere Illusion, die die bekannte Programmierpraxis in der Metaprogrammierung , in reflexiven Sprachen und in der Verwendung der evalFunktion nicht überlebt . In diesen Sprachen kann der Code vom laufenden Programm selbst unbegrenzt erweitert werden, solange der Computer ausgeführt wird. In der Tat könnte man Turing-Maschinen in Betracht ziehen, die ihre eigenen Übergangsregeln ändern und ihre Anzahl ungebunden erhöhen. Das kommt der Arbeitsweise von Universal Turing-Maschinen ziemlich nahe.

Bei der Gestaltung theoretischer Rahmenbedingungen besteht immer eine Spannung zwischen Einfachheit und Scharfsinn oder Ausdruckskraft. Die Einfachheit vereinfacht die Analyse des Frameworks häufig, insbesondere wenn es darum geht, bestimmte Eigenschaften nachzuweisen oder auf andere Frameworks zu reduzieren. Es ist jedoch oft unpraktisch, Konzepte auf hoher Ebene auszudrücken, die dann codiert werden müssen. Wir programmieren nicht mit Turing-Maschinen, sondern mit Hochsprachen, die viel ausdrucksvoller und übersichtlicher sind und gleichzeitig einige Hindernisse wie die Unterscheidung zwischen Code und Daten auf der Grundlage der semantischen Äquivalenz beseitigen können. Turingmaschinen scheinen einfach zu sein, können aber weit über ihre elementare Definition hinausgehen.

Die kurze Antwort: nein . Turing - Maschinen noch nicht alles unendlich an irgendeiner Stelle übernehmen.

Dies ist ein Grund, warum sie als Berechnungsmodell gültig sind. Es ist nicht sinnvoll, die Berechnung als etwas zu beschreiben, das von einem unendlichen Gerät ausgeführt wird.

Ihr Betrieb kann jedoch unendlich sein: Er kann nicht beendet werden. Dies ist ein weiterer Grund, warum sie als Berechnungsmodell gültig sind. Geräte, die nur Operationen ausführen können, bei denen garantiert ist, dass sie immer beendet werden, können nicht alle möglichen Berechnungen ausdrücken.

Darüber hinaus erfordert der Betrieb unbegrenzten Speicher: Während die tatsächlich verwendete Speichermenge immer begrenzt ist, kann sie beliebig groß werden. Sie können also nicht den gesamten Speicher bereitstellen, den eine Operation jemals im Voraus benötigt. Geräte, die nur Vorgänge ausführen können, bei denen garantiert nie mehr als eine bestimmte feste Speichermenge verwendet wird, können nicht alle möglichen Berechnungen ausdrücken.

"out of the box denken" und auf diese Frage verallgemeinern, die die Abstraktion von Turing-Maschinen auf den Punkt bringt, und einen anderen Blickwinkel finden, der noch nicht beantwortet wurde: Ja, Turing-Maschinen haben einige wesentliche Aspekte der "Annahme von Unendlichkeiten" da das Konzept der Mathematik innewohnt. TMs sind eine Abstraktion physischer Maschinen. Die physikalischen Konzepte von Zeit und Raum werden in der TM-Theorie absichtlich verwendet, aber als Abstraktionen, jedoch auch mit Aspekten ihrer realen Gegenstücke.

Kurz gesagt, das TM kann theoretisch möglicherweise für immer laufen , auch bekannt als das Problem des Anhaltens . Das Band ist unendlich, aber es kann immer nur eine begrenzte Menge davon zu einem bestimmten Zeitpunkt beschrieben werden. Ein TM, das für immer läuft, setzt grundsätzlich voraus, dass Zeit und Raum unbegrenzt sind, dh "unendlich". Tatsächlich gibt es eine entsprechende Zeit- und Raumhierarchie / "Kontinuum", die unendlich ist.

Eine physikalische Verwirklichung dieses abstrakten Konzepts ist jedoch nicht möglich, vorausgesetzt, das physikalische Universum ist begrenzt (Raum, Zeit, Materie, von denen die letzte etwas analog zu "Symbolen" oder "Tinte" in der Turing-Maschine ist). etwas ähnlich / analog wird in der Physik das Universum manchmal als unbegrenzt / unendlich angesehen, aber nur als Abstraktion. Um dies umzudrehen, ist das "Modellieren" eines modernen Computers als Turing-Maschine selbst eine Abstraktion, da der Computer nur endlichen Speicher usw. haben kann.

Ein weiterer nützlicher Vergleich ist die Zahlenreihe in der Mathematik. Die Zahlenreihe ist unendlich, bezeichnet aber endliche Zahlen. Jede Zahl auf der Zahlenlinie repräsentiert eine endliche Größe, aber es gibt eine unendliche Anzahl dieser endlichen Größen. Das Turing-Maschinenband hat eine starke Ähnlichkeit mit dem Zahlenlinienkonzept aus der Mathematik. Turing hätte es leicht als nur unendlich in einer Richtung definieren können, aber er definierte es als unendlich in beiden Richtungen, ähnlich wie die mathematische Zahlenlinie, mit negativen Positionen "links" auf dem Band und positiven Positionen "rechts".