Lücke zwischen

13

Wenn der Satz von Haltezeiten von Turing-Maschinen mit Zuständen auf einem binären Alphabet mit leerem Anfangsband ist, dann ist .HT(n)nBB(n)=maxHT(n)

Was können wir über die zweitgrößte Zahl in sagen ? Nenne das .HT(n)BB2(n)

BB2(n) ist trivial nicht berechenbar, da man damit berechnen kann : Warten Sie einfach, bis eine weitere Maschine anhält. Naiv würde ich erwarten, dass die Lücke "beschäftigt wie ein Biber" ist und schneller wächst als jede berechenbare Funktion. Ist das nachweisbar?BB(n)BB(n)-BB2(n)

computability Geoffrey Irving
quelle
Angenommen, einer der n Zustände ist nicht erreichbar.
mic
@mic: Ich halte das nicht für relevant. BB(n-1)=BB2(n) erscheint höchst unwahrscheinlich.
Geoffrey Irving
1
Dies hängt von der Kodierung ab. Wenn Sie die Zustände akzeptieren / ablehnen umdrehen, bleibt die Anzahl der Zustände gleich, ebenso wie die Zeit zum Anhalten, wodurch BB(n)=BB2(n) .
Lance Fortnow
6
Deshalb lasse ich die Menge der Haltezeiten sein, so dass die Lücke konstruktionsbedingt ungleich Null ist. HT(n)
Geoffrey Irving
1
Ist es überhaupt möglich zu beweisen, dass die Lücke nicht irgendwann 1 ist?
Geoffrey Irving

Antworten:

-1

  1. Die Anzahl der Zustände ist nur ein Begriff für die Komplexität der Beschreibung berechenbarer Funktionen in einem Modell. Sie können ein beliebiges Berechnungsmodell und eine beliebige Kodierung als binäre Zeichenfolgen auswählen und dann die Länge als n annehmen und BB (n) basierend auf definieren Das und all die interessanten Ergebnisse über BB (n) wären immer noch wahr, es gibt ein langweiliges Special über das TM-Modell und die Anzahl der Zustände.

  2. Nichts hindert sie daran, ein modifiziertes TM-Modell auszuwählen. Im Allgemeinen beziehen sich die Fragen, die unter solchen Änderungen der Darstellung von TMs nicht invariant sind, nicht auf die Berechenbarkeit oder TMs, sondern auf die bestimmte Darstellung (wie BB (n) mod 2 usw.), und wenn es keinen besonderen Grund dafür gibt, dass sie interessant sind, ziehen sie an lohnt sich nicht imho zu verfolgen. Sie sind schöne Rätsel, aber nicht von großem Wert. l Beachten Sie, dass "BB (n) nicht berechenbar ist" bei Änderung der Darstellung von TMs unveränderlich ist.

  3. Ist diese Frage also bei einer Änderung der Darstellung berechenbarer Funktionen unveränderlich? Die Antwort, die ich denke, ist nein.

ich. Stellen Sie sich eine Darstellung vor, in der wir zwei spezielle Zustände 0 und 1 haben und entweder 0 initial ist und nur zu 1 übergehen kann oder 0 nicht erreichbar ist und 1 initial ist. Bei dieser Codierung beträgt der Unterschied 1.

ii. Stellen Sie sich eine andere Darstellung vor, in der wir eine UTM plus einen Teil haben, der n Bits auf Band schreibt, bevor Sie zu UTM übergehen. Die Frage lautet also max f (x) - 2ndmax f (x), wobei die Maxima über n Bitketten liegen und f eine willkürlich berechenbare Funktion ist. Wir müssen nur eine berechenbare Funktion finden, bei der diese nicht berechenbar ist. Ich habe nicht viel darüber nachgedacht, aber mein Bauch sagt, dass es so eine berechenbare Funktion gibt.

Kaveh
quelle
2
Nichts davon ist relevant, weil ich Standard-Turing-Maschinen als meinen Begriff der Berechnung gewählt habe. Ich bin damit einverstanden, dass es ein paar verschiedene gemeinsame Definitionen gibt (einseitiges oder zweiseitiges Band, ob das Band mit Null beginnt oder ein spezielles leeres Symbol), aber nichts wie die vorcodierten UTMs, die Sie erwähnen.
Geoffrey Irving
1
Die Verwendung von zum Zählen einer völlig anderen Kodierung wäre eine andere und viel weniger interessante Frage, da, wie Sie sagen, die Kodierung so gewählt werden kann, dass die Frage zerbrochen wird. n
Geoffrey Irving
Lassen Sie es mich anders sagen: Warum interessiert Sie die Antwort? Es ist ein schönes Rätsel, wie viele andere über BB für eine bestimmte Darstellung von TMs, aber sie verraten nichts über die Berechenbarkeit und Berechnung. Die Auswahl des Standards für die Darstellung von TM war eine willkürliche Handlung, man hätte meine erste Darstellung oben auswählen können und die Antwort auf Ihre Frage wäre 1 gewesen. Nur weil es als Standard bezeichnet wird, ist es unter den Darstellungen nicht besonders.
Kaveh
Dies unterscheidet sich nicht von der Frage, ob eine willkürlich gewählte Diophantienne-Gleichung E eine ganzzahlige Lösung hat. Es gibt unendlich viele solcher Gleichungen, ohne einen Grund, warum man sich für E interessiert, ist es keine sehr interessante Frage. Wenn Leute Fragen wie "Berechenbarkeit von BB (n) mod 2" stellen, denken sie, dass sie tiefe Fragen zur Berechenbarkeit stellen, während es in Wirklichkeit eher so ist, als ob man nach der Löslichkeit einer willkürlich gewählten Diophantienne-Gleichung fragt das Auge.
Kaveh
2
Ich bin interessiert, weil ich glaube, dass die Antwort für alle nicht-numerischen Codierungen gleich ist: Es ist nicht beweisbar, es ist nicht beweisbar, dass es nicht beweisbar ist, usw. Aber ich weiß nicht, wie ich das ausdrücken soll, also habe ich eine ausgewählt. Die Tatsache, dass es für speziell ausgewählte Codierungen trivial ist, ähnelt dem Problem des Anhaltens, das für Maschinen lösbar ist, die sich nur für den Bau eignen.
Geoffrey Irving