Echte Computer haben nur eine begrenzte Anzahl von Zuständen. Welche Relevanz haben Turing-Maschinen für echte Computer?

42

Echte Computer haben nur begrenzten Speicher und nur eine begrenzte Anzahl von Zuständen. Sie sind also im Wesentlichen endliche Automaten. Warum verwenden theoretische Informatiker die Turing-Maschinen (und andere gleichwertige Modelle) zum Studium von Computern? Was bringt es, diese viel stärkeren Modelle in Bezug auf echte Computer zu untersuchen? Warum reicht das endliche Automatenmodell nicht aus?

Rahul
quelle
7
@Kaveh In der Regel wird von Hand gewiesen, dass es sich bei den in der Praxis verwendeten Computern um FSMs handelt, die jedoch zu groß sind und interessante Struktureigenschaften in der FSM-Ansicht verloren gehen. Ich habe noch nie eine nicht handwavy Erklärung gesehen. Daher ist die Frage hier zum Thema.
Martin Berger
15
Die eigentliche Frage ist, warum wir Turing-Maschinen untersuchen, wenn wir das RAM-Modell für die Analyse von Algorithmen verwenden.
Yuval Filmus
39
Denn manchmal ist eine bessere Annäherung an 100000000000000000000000000000 als 100000000000000000000000000000 . 1000000000000000000000000000000010000000000000000000000000000000
Andrej Bauer
30
Denken Sie daran, das bekannteste ungelöste Problem in der theoretischen Informatik ist heute: Kann eine Art physikalisch unmöglicher imaginärer Computer Probleme so schnell lösen wie ein noch physikalisch unmöglicherer imaginärer Computer ? Verwechseln Sie theoretische Informatik nicht mit praktischer Computertechnik. Die Details der physischen Welt sind nicht besonders relevant.
Eric Lippert
23
Reale Materialien bestehen aus Atomen und sind von Natur aus diskret. Warum also Integrale studieren?
Peter Shor

Antworten:

32

Bei der Betrachtung dieser Frage gibt es zwei Ansätze: historische, die sich darauf beziehen, wie Konzepte entdeckt wurden, und technische, die erklären, warum bestimmte Konzepte übernommen und andere aufgegeben oder sogar vergessen wurden.

Historisch gesehen ist die Turing-Maschine vielleicht das intuitivste Modell von mehreren, die versucht haben, das Entscheidungsproblem zu lösen . Dies hängt eng mit den Bemühungen der ersten Jahrzehnte des 20. Jahrhunderts zusammen, die Mathematik vollständig zu axiomatisieren. Die Hoffnung war, dass Sie, sobald Sie eine kleine Menge von Axiomen als richtig erwiesen haben (was einen erheblichen Aufwand erfordert), eine systematische Methode verwenden könnten, um einen Beweis für die logische Aussage abzuleiten, die Sie interessiert. Selbst wenn jemand endliche Automaten in Betracht zieht In diesem Zusammenhang würden sie schnell verworfen, da sie selbst einfache Funktionen nicht berechnen können.

Technisch ist die Aussage, dass alle Computer endliche Automaten sind, falsch. Ein endlicher Automat hat einen konstanten Speicher, der je nach Größe der Eingabe nicht geändert werden kann. Es gibt weder in der Mathematik noch in der Realität eine Einschränkung, die verhindert, dass zusätzliches Band, Festplatten, RAM oder andere Arten von Speicher bereitgestellt werden, sobald der Speicher in der Maschine verwendet wurde. Ich glaube, dies wurde in den frühen Tagen des Rechnens oft angewendet, als sogar einfache Berechnungen den Speicher füllen konnten, während dies für die meisten Probleme und mit der modernen Infrastruktur, die eine weitaus effizientere Speicherverwaltung ermöglicht, zumeist kein Problem ist .


BEARBEITEN: Ich habe beide in den Kommentaren angesprochenen Punkte berücksichtigt, habe mich jedoch dafür entschieden, sie nicht sowohl der Kürze als auch der Zeit wegen aufzunehmen, die mir zur Verfügung standen, um die Antwort aufzuschreiben. Dies ist meine Begründung, warum ich glaube, dass diese Punkte die Wirksamkeit von Turing-Maschinen bei der Simulation moderner Computer nicht mindern, insbesondere im Vergleich zu endlichen Automaten:

  • Lassen Sie mich zunächst das physikalische Problem einer Speicherbeschränkung durch das Universum ansprechen. Zunächst wissen wir nicht wirklich, ob das Universum endlich ist oder nicht. Darüber hinaus ist das Konzept des beobachtbaren Universums, das per Definition endlich ist, per Definition auch für einen Benutzer irrelevant, der zu einem beliebigen Punkt des beobachtbaren Universums reisen kann, um das Gedächtnis zu nutzen. Der Grund ist, dass sich das beobachtbare Universum auf das bezieht, was wir von einem bestimmten Punkt aus beobachten können, nämlich der Erde, und es wäre anders, wenn der Beobachter zu einem anderen Ort im Universum reisen könnte. Jede Argumentation über das beobachtbare Universum geht also in die Frage nach der Endlichkeit des Universums über. Nehmen wir jedoch an, dass wir durch einen Durchbruch das Wissen erlangen, dass das Universum tatsächlich endlich ist. Obwohl dies einen großen Einfluss auf wissenschaftliche Angelegenheiten haben würde, Ich bezweifle, dass dies Auswirkungen auf die Nutzung von Computern haben würde. Einfach ausgedrückt könnte es sein, dass die Computer im Prinzip tatsächlich endliche Automaten und keine Turing-Maschinen sind. Aber für die schiere Mehrheit der Berechnungen und aller Wahrscheinlichkeit nach für alle Berechnungen, an denen Menschen interessiert sind, bieten uns Turing-Maschinen und die dazugehörige Theorie ein besseres Verständnis. Obwohl wir wissen, dass die Newtonsche Physik im Wesentlichen falsch ist, bezweifle ich, dass Maschinenbauer in erster Linie die Quantenphysik verwenden, um Autos oder Fabrikmaschinen zu konstruieren. Die Eckfälle, in denen dies erforderlich ist, können auf individueller Ebene behandelt werden. Aber für die schiere Mehrheit der Berechnungen und aller Wahrscheinlichkeit nach für alle Berechnungen, an denen Menschen interessiert sind, bieten uns Turing-Maschinen und die dazugehörige Theorie ein besseres Verständnis. Obwohl wir wissen, dass die Newtonsche Physik im Wesentlichen falsch ist, bezweifle ich, dass Maschinenbauer in erster Linie die Quantenphysik verwenden, um Autos oder Fabrikmaschinen zu konstruieren. Die Eckfälle, in denen dies erforderlich ist, können auf individueller Ebene behandelt werden. Aber für die schiere Mehrheit der Berechnungen und aller Wahrscheinlichkeit nach für alle Berechnungen, an denen Menschen interessiert sind, bieten uns Turing-Maschinen und die dazugehörige Theorie ein besseres Verständnis. Obwohl wir wissen, dass die Newtonsche Physik im Wesentlichen falsch ist, bezweifle ich, dass Maschinenbauer in erster Linie die Quantenphysik verwenden, um Autos oder Fabrikmaschinen zu konstruieren. Die Eckfälle, in denen dies erforderlich ist, können auf individueller Ebene behandelt werden.

  • 264264verschiedene Adressen. Networking ist im Grunde eine großartige Methode, um dies zu erreichen. Jeder Computer kümmert sich nur um den lokalen Speicher, kann jedoch gemeinsam rechnen.

Chazisop
quelle
4
Der zweite Teil dieser Antwort ist falsch. Computer sind Automaten mit endlichen Zuständen, selbst wenn Sie den gesamten Arbeitsspeicher und andere Hardware gekauft haben, die Sie könnten. Die Größe des Arbeitsspeichers, den Sie an einen Computer anschließen können, ist durch die Breite seines Adressbusses begrenzt. Dies gilt auch für Festplatten und andere Peripheriegeräte.
Emil Jeřábek unterstützt Monica am
12
@ EmilJeřábek stimmt nicht. Serielle Schnittstellen verfügen nicht über einen Adressbus, und die Datenmenge, auf die ich im Internet zugreifen kann, wird durch keine Eigenschaft meines Computers eingeschränkt.
Hören Sie auf, Monica am
5
@OrangeDog, aber das Universum würde immer noch eine Grenze setzen, wie viele Daten im beobachtbaren Universum gespeichert werden können
Ratschenfreak
9
@ratchetfreak Wie die Turing-Maschine zeigt, benötigen Sie nur lokalen Zugriff - das aktuelle "Ende" des
Bands
6
Um die Geschichte zu erwähnen, ist es wert, die Rezension von Church zu Turing's Papier zu zitieren, dass Turing-Maschinen "den Vorteil haben, die Identifikation mit der Wirksamkeit ... sofort offensichtlich zu machen". Für die Menschen, die sich davon zu überzeugen versuchten, dass sie tatsächlich alles erfasst hatten, was berechnet werden konnte, war Turings Definition überzeugend.
Jim Hefferon
44

Um die anderen Antworten zu vervollständigen: Ich denke, dass Turing Machine eine bessere Abstraktion dessen ist, was Computer tun, als endliche Automaten. In der Tat besteht der Hauptunterschied zwischen den beiden Modellen darin, dass wir bei endlichen Automaten erwarten, dass Daten, die größer als der Zustandsraum sind, behandelt werden, und dass Turing Machine ein Modell für den umgekehrten Fall (Zustandsraum >> Daten) ist, indem der Zustand erstellt wird Raum unendlich. Diese Unendlichkeit kann als eine Abstraktion von "sehr groß vor der Größe der Daten" wahrgenommen werden. Wenn Sie ein Computerprogramm schreiben, versuchen Sie, aus Gründen der Effizienz Speicherplatz zu sparen, gehen jedoch im Allgemeinen davon aus, dass Sie nicht durch den gesamten Speicherplatz auf dem Computer eingeschränkt werden. Dies ist einer der Gründe, warum Turing Machines eine bessere Abstraktion von Computern sind als endliche Automaten.

Denis
quelle
14
Dies ist meiner Meinung nach die richtige Antwort. Die Gründe dafür sind rein pragmatisch. Turing-Maschinen können besser als endliche Automaten erklären, was Computer auf der Waage tun.
Emil Jeřábek unterstützt Monica am
3
Ich bin damit einverstanden, mit Ausnahme des Satzes "Sie gehen im Allgemeinen davon aus, dass Sie nicht durch den gesamten Speicherplatz auf dem Computer eingeschränkt werden". Im Gegenteil, fast jedes nicht-triviale Programm ist durch den verfügbaren Speicherplatz begrenzt, und Programmierer sind sehr bemüht, sich damit zu befassen (z. B. Speicherbereinigung für die automatische Wiederverwendung von Speicher), aber (1) wir können nichts dagegen tun, und (2) Wir beschränken uns auf ausreichend kleine Eingaben. Es ist bemerkenswert, dass TMs uns einen natürlichen Griff auf die Problemgröße geben und dass Algorithmen dazu neigen, in Bezug auf diesen natürlichen Begriff der Problemgröße nach unten geschlossen zu sein.
Martin Berger
2
@MartinBerger Re "Fast jedes nicht-triviale Programm ist durch den verfügbaren Speicherplatz begrenzt, und Programmierer sind sehr bemüht, sich damit zu befassen (z. B. Speicherbereinigung für die automatische Wiederverwendung des Speichers)": Ich würde behaupten, dass Programme, die für Systeme mit Speicherbereinigung geschrieben wurden, berücksichtigt werden Dieses System, einschließlich der gc , als die Maschine, gegen die sie programmieren. Der Garbage Collector ist nicht Teil des Programms. Es ist Teil der Bemühungen, genau das bereitzustellen, was Denis gesagt hat: Eine zu programmierende Maschine, für die praktisch unbegrenzte Speicherressourcen zur Verfügung stehen.
Peter - Reinstate Monica
2
@ PeterA.Schneider da stimme ich irgendwie nicht zu. Der Grund für die Verwendung des von der Sprachlaufzeit bereitgestellten GC ist eine der wirtschaftlichen Aspekte der Softwareentwicklung: Der programmspezifische Speicherverwaltungsmechanismus ist leistungsfähiger als der GC, und die meisten Programmierer würden es vorziehen, wenn sie ihn sicher und kostengünstig abrufen könnten. Aber sie können nicht, sondern gehen auf Nummer sicher und verwenden den Umgebungs-GC, dessen Kosten sich über eine große Anzahl von Programmen amortisieren. In diesem Sinne ist die Verwendung von GC sehr langwierig, um sich mit dem Endlichkeitsgedächtnis zu befassen.
Martin Berger
2
Turing-Maschinen sind keine Abstraktionen dessen, was Computer tun, sondern Abstraktionen dessen, was Computer tun, und danach wurden Computer gebaut. Computer führen die meisten ihrer Berechnungen mit einem festen internen Arbeitsspeicher durch, aber Turing Machines wurden nicht erfunden, um über die Berechnung mit einem begrenzten Arbeitsspeicher nachzudenken.
Reinierpost
10

Andrej Bauer gab in den Kommentaren einen wichtigen Grund an:

1000000000000000000000000000000010000000000000000000000000000000

Lassen Sie mich die anderen Antworten durch einige Punkte vervollständigen, die wahrscheinlich zu offensichtlich waren, um zu erwähnen:

  • Wenn es Ihr Ziel ist, echte Computer zu untersuchen, sind sowohl endliche Automaten als auch Turing-Maschinen häufig zu einfache Modelle für die relevanten Fragen. Echte Computer haben mehrere Prozessorkerne mit einer Cache-Hierarchie (oder einem anderen intelligenten Verwaltungsschema), Zugriff auf eine angemessene Menge an schnellem Speicher, Zugriff auf eine große Menge an langsamem externem Speicher (Festplatten) und können mit anderen ähnlichen Computern an einem Server kommunizieren Geschwindigkeit in etwa vergleichbar mit der Zugriffsgeschwindigkeit auf den langsamen externen Speicher.
  • Wenn Sie sich jetzt fragen, warum Sie all diese Details benötigen, stellt sich heraus, dass Ihr eigentliches Ziel darin besteht, Problemfälle zu untersuchen und wie effizient Sie sie lösen können. Wenn es sich um echte Computer handelt, kann dies auch bedeuten, dass Sie Experimente mit tatsächlichen Probleminstanzen auf verschiedenen Arten von (realen) Computerarchitekturen durchführen.
  • Das oben beschriebene Modell realer Computer ist immer noch idealisiert, da es die verschiedenen Fehlermodi realer Computer ignoriert. Da Stromausfälle häufiger auftreten als Festplattenausfälle (und Festplatten haben möglicherweise ohnehin Backups), muss dies möglicherweise in bestimmten Problemdomänen wie dem zuverlässigen Datenbankbetrieb berücksichtigt werden.
  • Π10
Thomas Klimpel
quelle
8

Ein Formalismus ist nützlich oder nicht, basierend darauf, was die Leute mit dem Formalismus modellieren und verstehen wollen.

Die Turing-Maschine ist ein Formalismus, der zum Verständnis von Programmen hilfreich ist . Programme sind es wert, verstanden zu werden; Die meisten Berechnungen werden von Programmen und nicht von Spezialmaschinen durchgeführt. Mit dem Turing-Maschinenformalismus können wir wichtige reale Belange wie Zeit- und Raumkomplexität modellieren. Es ist weitaus weniger selbstverständlich, diese Begriffe unter Verwendung von Automaten mit endlichen Zuständen zu untersuchen.

Turing-Maschinen sind nicht sehr nützlich, wenn Sie versuchen, die Komplexität der Berechnung endlicher Funktionen zu untersuchen (z. B. Funktionen, deren Domäne aus Eingaben mit einer Länge von höchstens 10 Millionen besteht). Die Komplexität von Schaltkreisen kann die Komplexität von endlichen Funktionen viel besser beschreiben ... Turing-Maschinen waren jedoch wiederum sehr nützlich, um die Komplexität von Schaltkreisen zu verstehen.

Endliche Automaten waren auch nützlich, um die Komplexität von Schaltungen zu verstehen. Alle diese Modelle haben ihren Platz im mathematischen Arsenal.

Ich lehne das Argument ab, dass Automaten mit endlichen Zuständen ein besseres Modell der Realität sind, nur weil reale Computer nur eine begrenzte Anzahl von internen Zuständen haben. Die Untersuchung von Automaten mit endlichen Zuständen befasst sich entscheidend mit Eingaben aus der unendlichen Menge von Zeichenfolgen, wohingegen Computer in der realen Welt nur Eingaben mit einer festgelegten maximalen Länge verarbeiten (es sei denn, Sie glauben, dass wir räumlich in einem unendlichen Universum leben) oder Zeit).

Ein Modell sollte in Bezug auf seine Nützlichkeit beurteilt werden, um die Aspekte der Realität zu verstehen, die uns wichtig sind. Oder (alternativ) in Bezug auf die Nützlichkeit, ein mathematisches Universum zu verstehen, das die Menschen als ausreichend überzeugend empfinden, selbst wenn dieses mathematische Universum keine offensichtliche physikalische Manifestation aufweist.

Turingmaschinen, Zustandsmaschinen und Schaltkreise (und andere Modelle) haben sich alle als nützlich erwiesen.

Eric Allender
quelle
6

Tatsächliche Computer sind keine FSAs. Ein tatsächlicher Computer ist ein universeller Computer in dem Sinne, dass wir einen Computer beschreiben können, den ein Computer emulieren soll, und der Computer wird ihn emulieren. Suchen Sie für viele Beispiele nach "virtueller Maschine".

Es ist möglich, eine Universal-Turing-Maschine zu konstruieren - ein TM, das eine Beschreibung eines anderen TM empfängt, emuliert dann den Betrieb dieses TM an einem bereitgestellten Eingang.

n22n

Als Ausgangspunkt für die Literatur kann ich " On the Existence of Universal Finite oder Pushdown Automata " empfehlen , das die Nichtexistenz von Universalautomaten untersucht. Sie können sich auch die Referenzen ansehen (und so weiter).

Eric Towers
quelle
3
Dies ist ein nützlicher Ansatz, um verschiedene Ebenen der „Rechenleistung“ intuitiv zu erfassen. OP scheint jedoch zu glauben, dass echte Computer FSMs sind, da die Anzahl der Zustände begrenzt ist, z. B. aufgrund von endlichem RAM. Ihrer Meinung nach sind echte Computer eher FSMs als Turing Machines, da ich die Anzahl der Zustände in einer simulierten Maschine nicht frei verdoppeln kann. Ich habe kein unendliches Band als Speicher.
Amon
1
Turing Machines brauchen auch kein Endlosband. Computer können eine willkürlich große Menge an externem Speicher für ihre Berechnungen verwenden (und dies wird bei den heutigen Cloud-Anbietern besonders einfach), sodass sie im Grunde eher Turing Machines als FSMs ähneln.
Reinierpost
1
Wenn wir davon ausgehen, dass ein Computer über eine feste Speichermenge verfügt, wird ihm der Speicher ausgehen, wenn ein Computer mit mehr Speicher simuliert wird. Daher ist diese Annahme nicht wirklich universell.
Kaveh
3

Das Besondere an der Turing-Maschine ist, dass sie zwar sehr, sehr einfach ist, aber alle (Klassen von) Algorithmen ausführen kann, die wir uns vorstellen können. Es ist keine leistungsstärkere Maschine bekannt (da sie Algorithmen ausführen kann, zu denen die Turing-Maschine nicht in der Lage ist).

Aufgrund der einfachen Mechanik lässt sich leicht zeigen, ob oder in welchem ​​Maße andere Maschinen einer Turing-Maschine entsprechen. Dies macht es wiederum relativ einfach zu zeigen, ob ein bestimmter Computer (oder eine bestimmte Computersprache) wirklich universell ist (c / f "Turing-complete").

AnoE
quelle
Die Frage ist nach der Beziehung des Turing-Maschinenmodells zu realen Computern. Wenn wir davon ausgehen, dass ein Computer über einen festen Speicher verfügt, ist er nicht wirklich universell.
Kaveh
1

Warum reicht das endliche Automatenmodell nicht aus?

Während andere Antworten bereits viele relevante Aspekte erwähnt haben, glaube ich, dass der größte Vorteil von Turing-Maschinen gegenüber endlichen Automaten die Trennung von Daten und Programmen ist . Auf diese Weise können Sie ein ziemlich endliches Programm analysieren und Aussagen darüber treffen, wie dieses Programm mit unterschiedlichen Eingaben umgehen würde, ohne die Größe der Eingabe einzuschränken.

Während es theoretisch möglich ist, sowohl einen tatsächlichen Computer als auch so etwas wie eine Turing-Maschine mit endlichem Band als Zustandsmaschine zu beschreiben, ist dies nicht wirklich realisierbar: Die Anzahl der Zustände ist exponentiell in Bezug auf die Speicherkapazität Ihrer Maschine und die allgemeine Endlichkeit Für den Statusautomat-Formalismus müssen Sie die Übergänge zwischen diesen Status explizit auflisten. Für einen allgemeinen Automaten mit endlichen Zuständen dieser Größe ist es daher ziemlich unmöglich, irgendwelche Ableitungen auf der Grundlage einer vollständigen Aufzählung aller Zustandsübergänge vorzunehmen.

Natürlich können Zustandsübergänge in einem echten Computer nicht willkürlich erfolgen. Es gibt keinen Befehl, um ein Drittel der Bits im Speicher in einem einzelnen Schritt der Berechnung auszutauschen. Sie könnten also versuchen, eine kompaktere Spezifikation für die Zustandsübergänge zu finden. So etwas wie die Befehlssatzspezifikation Ihrer Architektur. Echte Computerarchitekturen sind natürlich aus Performancegründen kompliziert, daher können Sie dies mit einem sehr einfachen Befehlssatz weiter vereinfachen, der nur sehr kleine Schritte mit sehr begrenzter Eingabe und Ausgabe ausführt. Am Ende stellen Sie möglicherweise fest, dass Ihre Architektur einem Turing-Maschineninterpreter ähnelt: Verwenden Sie einige Bits Programmcode und ein Bit Eingabe, generieren Sie ein bisschen Ausgabe und bewegen Sie sich in Ihrem Programmcode.

Eine Alternative wäre die Verwendung der Zustände eines Automaten mit endlichen Zuständen, um nur die vom Programm verarbeiteten Daten darzustellen, während das Programm selbst in die Zustandsübergänge codiert wird. Das würde das gleiche Problem mit sich bringen, wie alle Zustände gezählt werden sollen, und eine kompakte Darstellung könnte wieder in der Nähe dessen sein, was eine Turing-Maschine tut.

Was bringt es, diese viel stärkeren Modelle in Bezug auf echte Computer zu untersuchen?

Insgesamt würde ich sagen, dass eine Turing-Maschine mit endlichen Bändern wahrscheinlich ein besseres Modell für tatsächliche Computer wäre. Bei vielen wissenschaftlichen Fragen ist die Unterscheidung zwischen einem endlichen, aber großen und einem unendlichen Band irrelevant. Wenn Sie also nur ein unendliches Band beanspruchen, wird die Sache einfacher. Bei anderen Fragen steht die Menge des verwendeten Bandes im Mittelpunkt der Frage. Mit dem Modell können Sie jedoch problemlos über den Umfang der Bandnutzung sprechen, ohne angeben zu müssen, was passiert, wenn für die Berechnung kein Band mehr zur Verfügung steht.

MvG
quelle
1

Die meisten Probleme erfordern Turingmaschinen mit begrenzter Größe

Obwohl angenommen wird, dass unbegrenztes Band eine nützliche Vereinfachung darstellt, erfordern die meisten Probleme / Algorithmen tatsächlich eine begrenzte Menge an Band, und die Grenzen des erforderlichen Speichers (möglicherweise abhängig von der Größe der Eingabe) können analysiert und häufig bewiesen werden.

Dies lässt sich auch häufig auf andere Computertypen übertragen (für die gebundene Analysen oder Beweise möglicherweise sehr viel unübersichtlicher sind als auf einer Turing-Maschine) und ermöglicht die Schätzung des für ein bestimmtes Problem erforderlichen temporären Speichers - kann dies in einer festgelegten Menge erfolgen Raum? Proportional zum Eingang? Benötigt es exponentiell viel Platz, wenn die Eingaben zunehmen?

Peter ist
quelle
1

Ein wichtiges Merkmal von Turing-Maschinen, die von endlichen Automaten nicht gemeinsam genutzt werden, ist, dass sie die zur Lösung des Problems erforderliche Speichermenge an die Größe des Problems anpassen können .

nn2

Der Punkt: Viele Probleme haben natürliche Lösungen, die mehr Speicher belegen, je größer das Problem ist. Daher ist es selbstverständlich, diese Lösungen mit Darstellungen zu beschreiben, die unendlichen Speicher verwenden können - nicht, weil eine Instanz unendlich viel davon verwendet, sondern weil es eine Instanz gibt, die jede Menge verwendet. Das geht mit Turingmaschinen, aber auch mit Sequenzen endlicher Automaten.

josinalvo
quelle
Wenn eine Turing-Maschine mit N Zuständen mit einem Band gestartet wird, das eine endliche Anzahl von C nicht-leeren Zeichen vor und nach der Anfangsposition hat, gibt es eine gewisse Anzahl T (N, C), so dass jede Maschine welche jemals enden wird, könnte von einer Maschine emuliert werden, deren Band auf T (N, C) Zeichen beschränkt war.
Supercat
-2

Echte Computer haben nur begrenzten Speicher und nur eine begrenzte Anzahl von Zuständen. Sie sind also im Wesentlichen endliche Automaten.

Turingmaschinen sind Derivate endlicher Automaten. Turingmaschinen sind praktisch von Nuemann Architektur.

Jesse Enjaian
quelle