Ich lese das Buch Computational Complexity: Eine moderne Herangehensweise und ich habe Probleme, <> starke Turing-Maschinen zu verstehen.
Eine unachtsame Turing-Maschine (TM) ist eine solche TM, dass die Bewegung ihrer Köpfe ausschließlich durch die Länge der Eingabe bestimmt wird. Das heißt, das TM ist sich seiner Eingabe nicht bewusst. So weit so gut.
Aber eine der Übungen soll den folgenden Satz beweisen:
%Vor% Es ist offensichtlich, dass das nicht erkennbare TM nicht auf der ursprünglichen Eingabe von L , sondern bei einigen codierten Versionen arbeiten muss. Das heißt, der Kern des Theorems ist die Codierung einer Bitstring zu einer ganzen Zahl (Länge der Eingabe des nicht erkennbaren TM). Aber wenn man die Menge der möglichen Eingaben von L (Bitstrings) zu einer ganzen Zahl kodieren möchte, würde man relativ schnell sehr hohe Zahlen erreichen, da 2^n Bitstrings der Länge n vorhanden sind.
Verstehe ich das Problem richtig? Wie beweisen Sie den Satz?
Hier empfehle ich Ihnen, dieses Papier zu lesen. Es ist ein ziemlich interessantes und wundervolles Papier, das Ihnen einen Beweis zu einer niedrigeren Zeitgrenze geben wird, die angefordert hat. (Ich denke, Sie sollten es als O (N ^ 2) finalisieren können, oder Sie könnten schließen, dass O (N * log (N)) technisch O ist (N ^ 2), aber das Befolgen dieses Beweises könnte Ihren Professor verärgern. Ich nehme an, er beabsichtigt, dass Sie es anders angehen.
Bearbeiten:
Der ursprüngliche Link zum Papier funktioniert nicht mehr. Hier ist eine weitere öffentlich gepostete.
"Beziehungen zwischen Komplexitätsmaßen" von Michael J. Fischer und Nicholas Pippenger, 1979.
Tags und Links computer-science turing-machines