Warum ist das eine ungültige Turing-Maschine?

Question

Während tun Prüfung Revision Ich habe Probleme, die folgende Frage aus dem Buch zu beantworten: „Eine Einführung in die Theorie der Berechnung“ von Sipser. Leider gibt es keine Lösung für diese Frage in dem Buch.

Erklären Sie, warum die folgende ist keine legitime Turing-Maschine.

M = {

Der Eingang ist ein Polynom p über Variablen x1, ..., xn

Versuchen
1. alle möglichen Einstellungen von x1, ..., xn auf ganzzahlige Werte
2. Ausrechnen p auf all diese Einstellungen
3. Wenn eine dieser Einstellungen auf 0 auswertet, akzeptieren; sonst ablehnen. }

Das macht mich verrückt! Ich vermute, es liegt daran, dass die Menge der ganzen Zahlen unendlich ist? Ist das irgendwie das Alphabet der zulässige Größe überschreiten?

Answer 1

Das ist zwar durchaus eine informelle Art und Weise eine Turing-Maschine zu beschreiben, würde ich sagen, das Problem ist eine der folgenden:

• otherwise reject - Ich stimme mit Welbog darauf. Da Sie eine abzählbar unendliche Menge möglicher Einstellungen haben, kann die Maschine nie wissen, ob eine Einstellung auf dem es auf 0 wertet noch kommen wird, und schlingt immer wenn es ein nicht findet - nur dann, wenn eine solche Einstellung auftritt, kann die Maschine stoppen. Diese letzte Aussage ist nutzlos und wird nie wahr sein, es sei denn natürlich Sie das Gerät an eine endliche Menge ganzer Zahlen begrenzen.

• Der Code Bestellung: Ich würde diesen Pseudo-Code lesen als „erster Schreib alle möglichen Einstellungen nach unten, dann p auswerten auf jedem“, und es ist Ihr Problem: Wiederum durch eine unendliche Menge von möglichen Einstellungen mit, nicht einmal der erste Teil wird jemals beenden, weil es nie eine letzte Einstellung mit dem nächsten Schritt aufschreiben und fortzusetzen. In diesem Fall kann nicht einmal die Maschine nie sagen, „es gibt keine Einstellung 0“, aber es kann auch nie starten Auswertung zu finden. Auch dies durch eine Begrenzung der Menge ganzer Zahlen gelöst werden würde.

Wie auch immer, ich glaube nicht, das Problem die Größe des Alphabets ist. Sie würden nicht in geschrieben werden, ein unendliches Alphabet da Ihre ganzen Zahlen Dezimal / Binär / etc verwenden können, und solche, die nur ein (sehr) endliches Alphabet verwenden.

Answer 2

Ich bin ein bisschen rostig auf Turing-Maschinen, aber ich glaube, Ihre Argumentation richtig ist, dh die Menge der ganzen Zahlen unendlich ist daher können Sie nicht alle berechnen. Ich bin nicht sicher, wie dies obwohl theoretisch zu beweisen.

Allerdings ist der einfachste Weg, Ihren Kopf um Turing-Maschinen zu bekommen, ist daran zu erinnern, „Alles, was ein echter Computer berechnen kann, eine Turing-Maschine kann auch berechnen.“. Also, wenn Sie ein Programm schreiben können gegeben, dass ein Polynom Ihre drei Fragen lösen kann, werden Sie in der Lage sein, eine Turing-Maschine zu finden, die es auch tun können.

Answer 3

Ich denke, das Problem ist mit dem allerletzten Teil: otherwise reject.

Nach abzählbar Grundlagen jeder Vektorraum über einen abzählbar ist zählbar selbst. In Ihrem Fall haben Sie einen Vektorraum über die ganzen Zahlen von Größe n, die zählbar ist. So Ihre Menge der ganzen Zahlen zählbar ist und daher ist es möglich, jede Kombination von ihnen zu versuchen. (Das heißt, ohne irgendeine Kombination fehlt.)

Auch auf einem bestimmten Satz von Eingaben des Ergebnisses p Berechnung ist ebenfalls möglich.

Und die Eingabe eines akzeptierenden Zustand, wenn p auswertet auf 0 ist ebenfalls möglich.

Da es eine unendliche Anzahl von Eingangsvektoren ist, können Sie nie verwerfen Sie die Eingabe. Daher ist keine Turing-Maschine kann in der Frage definiert alle Regeln folgen. Ohne diese letzte Regel ist es möglich.