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:
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 ?
turing-machines
halting-problem
Akkumulation
quelle
quelle
Antworten:
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.
quelle