Wie gut kann ein Stillstandsmelder sein?

12

Gibt es eine Turingmaschine, die entscheiden kann, ob fast alle anderen Turingmaschinen anhalten?

Angenommen, wir haben eine Aufzählung von Turing-Maschinen und eine Vorstellung von der "Größe" einer Menge natürlicher Zahlenund wir definieren:N{Mi}

f(i)={n:Mi can't decide whether Mn halts}.

Welche Charakterisierungen des Minimalwertes von gibt es für verschiedene \ | \ cdot \ | ? Angenommen, \ | S \ | ist der Limsup des Anteils von Zahlen bis zu k , die in S sind . Gibt es ein i für das f (i) = 0 ist ?fSkSif(i)=0

Akkumulation
quelle
4
projecteuclid.org/euclid.ndjfl/1168352664
Emil Jeřábek unterstützt Monica

Antworten:

10

Dies ist keine "nette" Eigenschaft, da es von der Codierung abhängt, ob sie wahr oder falsch ist.

Siehe David et al. Asymptotisch sind fast alle Terme stark normalisierendλ , was beweist, was im Titel steht. Diese Arbeit zeigt jedoch auch, dass das Gegenteil für SKI-Kombinatoren gilt (in die Lambda-Terme kompositorisch eingebettet werden können).

Im Lambda-Kalkül entspricht eine Reduktion einem Schritt einer Turing-Maschine, und eine starke Normalisierung ist die Eigenschaft, dass jede Reduktionssequenz schließlich eine normale Form erreicht - dh es sind keine weiteren Reduktionen möglich. (Da ein gegebener Lambda-Term viele gültige Verringerungen haben kann, ist eine starke Normalisierung ein bisschen so, als würde man sagen, dass eine gegebene nicht deterministische Turing-Maschine immer anhält.) Die Tatsache, dass asymptotisch fast alle Terme stark normalisieren, bedeutet also, dass sich mit einer Wahrscheinlichkeit von 1 die Verringerungen nähern große Lambda-Terme erreichen immer eine normale Form.λ

Lambda-Terme können jedoch bedeutungserhaltend in einen Kombinationskalkül wie die SKI-Kombinatoren (und umgekehrt) und in Kombinationskalküle asymptotisch in eine Schleife aller Terme übersetzt werden.

Neel Krishnaswami
quelle
2
Ich stelle fest, dass ein zukünftiger Besucher, der nicht unbedingt die Beziehung zwischen starker Normalisierung und Anhalten der Erkennung kennt, möglicherweise nicht in der Lage ist, zu bestimmen, welche Position (falls vorhanden) Ihre Antwort einnimmt.
Eric Towers
@EricTowers Fertig!
Neel Krishnaswami