Was ist Turing -Vollständigkeit?

Vollständigkeit ist, wenn eine Programmiersprache die Funktionen einer Turing -Maschine ausführen kann. Dies ist ein Konzept für einen sehr grundlegenden mechanischen Computer, der manchmal als die einfachste Maschine bezeichnet wird, die als Computer angesehen werden kann. Praktisch alle Programmiersprachen, die heute verwendet werden, und theoretisch sind die Computer, die sie ausführen, die Vollständigkeit. Zu seinen Arbeiten zum Computer gehörte die Entwicklung einer Philosophie dessen, was ein Computer tatsächlich tun konnte. Dies beinhaltete das Konzept, dass Computer einfach durch Ausführen von Algorithmen funktionieren. Das heißt, sie befolgen einen festen Satz von Regeln, um Daten zu verarbeiten und Probleme zu lösen. Dies bedeutet

Um das Konzept zu veranschaulichen,Turing beschrieb eine hypothetische Maschine, die er als "A-Maschine" bezeichnete, wobei das "A" für automatisch stand; Andere nannten es später die Turing -Maschine. Die Maschine würde eine Klebebandspule verarbeiten, die sich zurück oder nach vorne bewegen und eine Reihe von Symbolen enthielt. Die Maschine kann jederzeit ein Symbol verarbeiten und bei Bedarf es ändern. Für die Zwecke des Konzepts könnte die Klebebandtrolle unendlich lang sein, was bedeutet, dass der Speicher des Computers nicht von Natur aus begrenzt war. Dies ist eine Analogie für die Idee, dass ein Computer, sobald er eine Reihe von Anweisungen befolgt hat, die Datenmenge, auf die er angewendet werden kann, nur für physische Grenzen unterliegt.

Ironischerweise haben die meisten Computer heute keine Vollständigkeit. Dies liegt daran, dass sie Einschränkungen für den verfügbaren Speicherplatz und damit die Daten haben, die sie verarbeiten können. Sie haben auch körperliche Einschränkungen, vor allem, dass sie sich irgendwann abnutzen werden. Es ist tatsächlich die Programmiersprache, die Vollständigkeit hat.Aus diesem Grund ist ein Computer, der ein solches Programm ausführt, kein Turing -Computer, sondern kann verwendet werden, um eines zu simulieren.

Vollständigkeit sollte nicht mit dem Turing -Test verwechselt werden. Dies war ein von Turing entworfenes Experiment, um festzustellen, ob Computer in der natürlichen Sprache unterhalten werden können. Das Prinzip des Tests ist, dass der Computer den Test bestehen kann, wenn ein Mensch den Unterschied zwischen einer nur Textkonversation mit dem Computer und einem anderen Menschen erkennen kann. Während einige Computer den Test bestanden haben, wenn der Bereich der Konversationsthemen eingeschränkt ist, hat dies in uneingeschränkter Konversation keiner durchgeführt.