Universelle Turing-Maschine Probleme

Question

Wenn ich eine Maschine haben, rufen Sie es Maschine 1, das in der Lage ist, ein Problem zu lösen: es ist nur eine Maschine, nicht per se eine Turing-Maschine. Es kann ein bestimmtes Problem lösen. Wenn dies genau die gleiche Problem auf einer Universal-Turing-Maschine gelöst wird, dann ist meine ursprüngliche Maschine, 1, eine Universal-Turing-Maschine zu?

Dies gilt nicht für alle Probleme, die bereits ansered. Gibt es Probleme, die diese Eigenschaft überhaupt beschrieben haben? Wenn es absolut nicht wahr ist, dann warum?

Kann jemand ein Beispiel für ein Problem geben, gelöst werden. Wenn dieses Problem durch meine ursprüngliche Maschine gelöst, 1, macht auf jeden Fall diese ein Universal-Drehmaschine? Oder ist ein solches Problem existiert nicht? Wenn es nicht existiert, warum?

Ich bin sehr interessiert, aber kann es nicht herausfinden ... Danke.

Edit:. Hat die Frage deutlicher

Answer 1

Der Punkt des Universal-Drehmaschine (UTM) ist, dass für jede Turingmaschine (TM) Sie, dass TM zu nehmen und schaffen eine Codierung für es, das den Betrieb des TM beschreibt und haben diese auf einem anderen TM kodiert laufen.

Die UTM ist ein TM, die eine Definition stark genug hat, so dass jede andere TM Definition in ihm neu geschrieben werden.

Denken Sie an die UTM als Dolmetscher. Die TM ist eine spezifische Aufgabe.

Es sei denn, die TM auch in der Klasse der Dolmetscher ist, dann ist es kein UTM auch. (Da eine UTM ist auch ein speziell beauftragt TM).

So Ihre zweite Frage zu beantworten: wenn Sie nachweisen können, dass die UTM und TM äquivalent sind, dann haben Sie gezeigt, dass TM ist auch eine UTM. Um dies zu tun Sie müssen in der Lage zu zeigen, wie ein codiertes Programm für die UTM kann in ein äquivalentes Programm für die TM geändert werden.

Answer 2

Ein Universal-Turing-Maschine kann eine beliebige einer großen Klasse von Problemen lösen.

Wenn Ihre Maschine (1) 1 + 1 lösen kann, dass es bedeutet nicht, jede der großen Klasse lösen kann. So ist es kein Universal Turing-Maschine.

sein kann

Answer 3

Die Logiker unterscheiden zwischen „ausreichend“ und „notwendig“ Bedingungen. Nehmen wir zum Beispiel den Satz

  

Der Himmel ist blau.

(lassen Sie sich einfach davon ausgehen, das ist immer wahr). Was Sie jetzt wissen, ist dies:

  

Wenn Sie in den Himmel schauen, sehen Sie die Farbe Blau.

Was Sie nicht wissen, ist dies:

  

Wenn Sie die Farbe Blau zu sehen, sind Sie in den Himmel schauen.

-. Sie könnte genauso gut sein Blick auf dem Auto des Nachbarn

In logischen Begriffen, die Farbe Blau ist notwendig für den Himmel, aber es ist nicht ausreichend.

Das gleiche gilt für Ihren Fall: Maschine (1) Ihr Problem löst, es ist so in der Tat ein lösbares Problem. Daher das Problem zu lösen in der Lage ist, eine notwendig Bedingung für eine UTM, aber nicht ausreichend ein, weil eine UTM Lage sein müssen, lösen jeder Problem (das auflösbar ist bei alle), nicht nur diese einzelne.

Answer 4

Eine universelle Turing-Maschine mit einem beliebigen Code lösen kann, dass jede spezifische Turingmaschine lösen kann.

So Ihre universelle Turing-Maschine (2) kann das Problem lösen, dass Ihre ursprüngliche Turingmaschine (1) wurde entwickelt, um zu lösen.

Ihre ursprüngliche Turingmaschine (1) kann jedoch lösen nur die genaue Problem und andere Probleme nicht lösen kann (einschließlich dem „Problem“ von einer universellen Turing-Maschine ist).

Also nein, Ihre ursprüngliche Turing-Maschine ist keine universelle Turing-Maschine nach Ihrer Beschreibung. (Es könnte sein, wenn das Sie es definieren, aber das ist eine Art von Betrug).

Answer 5

  

Kann jemand ein Beispiel für ein Problem geben, gelöst werden.

Sicher:. Bei codierter Maschine und Daten drehen, was ist das Ergebnis :) Wenn Ihr Gerät kann dieses Problem löst, ist es sicherlich UTM

Kennen Sie die Argumentationslinie, warum die verschiedenen Probleme in NP sind? Wie ‚i die lösen kann 3-sat Problem, wenn ich eine Maschine, dass löst das Hamilton-Problem?‘ Sie können sicherlich die gleiche benutzen, um Ihre Frage zu beantworten.

Answer 6

Der Beweis der Turing Vollständigkeit eines bestimmten Systems ist nicht trivial, wenn man leicht nachweisen kann, dass es äquivalent / isomorph zu einem anderen System, das weiß ist, werden Turing abgeschlossen. So kurze Antwort: Es gibt keinen einfachen Test, dass Sie Ihre Maschine bis hin zur Überprüfung stellen kann, ob es vollständig ist Turing. Sie müssen analysieren und zeigen Eigenschaften des Systems als Ganzes.

Wenn Sie mehr über dieses Thema erfahren wollen, lesen Sie diese Artikel über Turing Vollständigkeit und Berechenbarkeit Theorie .

Answer 7

Stellen Sie sich eine UTM als ob, wie würden Sie vorgehen, wenn Sie die Turing machine.You zur Simulation eines Codes (High-Pegel) zu schreiben, haben die folgenden benötigen: 1.Array die Eingangssymbole und das Zeug zu halten, dass yiu auf es tun würde. 2.An Array (mögliche 2-d) die Übergangsfunktion zu halten, dass sie den Benutzer auffordern wird. 3.An Algorithmus, der Benutzer-Eingaben von Übergangsfunktionen gelesen und simuliert er auf Array-1. 4.Few Variablen, dass Ihr Programm benötigen, um ihren eigenen Zustand zu verfolgen.

Wenn Sie auf diese Weise denken, wenn Sie einen am Ende immer perfekt funktionierenden Code Sie mit einem perfekten UTM enden. Allerdings ist der Haken, egal wie effizient Code, den Sie Sie den Benutzer nicht von der Eingabe Übergangsfunktionen stoppen können, die Ihr Code kann dazu führen, laufen forever.So wird es bestimmte Probleme, für die UTM ausfallen, und dann sagen wir, dass für diese Probleme wir können keine Mitgliedschaft Testmaschine entwickeln. (obwohl Bekanntmachung Mitgliedschaft Überprüfung Maschine immer möglich ist)