Ein interessanter metrischer Raum im Zusammenhang mit Turingmaschinen

In dieser Frage werden nur Turing-Maschinen betrachtet, die bei allen Eingaben anhalten. Wenn $k \in \mathbb{N}$ dann bezeichnen wir mit $T_k$ die Turingmaschine, deren Code $k$ .

Betrachten Sie die folgende Funktion

Mit anderen Worten, ist der Code der kleinsten Turingmaschine, die genau eine der Zeichenfolgen erkenntWir können nun die folgende Karte definierenx , y $s(x,y)$$x,y.$

Es kann schnell überprüft werden, dass einen metrischen Raum (in der Tat eine Ultrametrik) auf induziertΣ ∗$d(x,y)$$\Sigma^{*}.$

Nun möchte ich beweisen, dass, wenn eine gleichmäßig stetige Funktion ist, für jede rekursive Sprache ebenfalls rekursiv ist. f - 1 ( L $f:\Sigma^{*} \mapsto \Sigma^{*}$$f^{-1}(L)$

Mit anderen Worten sei eine Map, so dass für jedes ein so dass für die Strings dann Dann müssen wir zeigen, dass eine rekursive Sprache ist, da rekursiv ist.ε > 0 δ > 0 x , y ∈ & Sigma; $f$$\epsilon > 0$$\delta > 0$$x,y \in \Sigma^{*}$ d ( f ( x ) , f ( y ) ) < ϵ . f - 1 ( L )

Wie bereits in diesem Beitrag erwähnt, besteht eine Möglichkeit, das Problem anzugehen, darin, zu zeigen, dass es eine Turing-Maschine gibt, die mit einer Zeichenfolge berechnet f ( x ) $x \in \Sigma^{*}$$f(x).$

Ich stecke fest, um diese Behauptung zu beweisen, und frage mich langsam, ob es einen anderen Ansatz gibt, um dies zu lösen?

Hinweise, Vorschläge und Lösungen sind willkommen!

Bearbeiten: Hinweise entfernt, meine Lösung gepostet.

Hier ist meine Lösung. Wir wählen einen Referenzpunkt dem und betrachten das Universum aus der Sicht von und . Es stellt sich heraus, dass jede "Nachbarschaft" eines Punktes einer rekursiven Sprache entspricht. Also ist eine Nachbarschaft um , und es wird eine Nachbarschaft um , die darauf abgebildet ist; Diese Nachbarschaft ist eine rekursive Sprache.f ( x ) ≤ L x f ( x ) L f ( x ) $x$$f(x) \in L$$x$$f(x)$$L$$f(x)$$x$

Lemma. In diesem Raum ist eine Sprache genau dann rekursiv, wenn sie sich in der Nachbarschaft der einzelnen Zeichenfolgen befindet.

Beweis . Zuerst fixiert eine rekursive Sprache und lassen . Lassen der Minimal - Index eines Entscheiders für sein . Dann haben wir , dass , wenn , , so . Somit impliziert , dass .x ≤ $L$$x \in L$L y ∉ L s ( x , y ) ≤ K d ( x , y ) ≥ 1 / 2 K d ( x , y ) < 1 / 2 K y ∈ $K$$L$$y \not \in L$$s(x,y) \leq K$$d(x,y) \geq 1/2^K$$d(x,y) < 1/2^K$$y \in L$

Zweitens sei eine beliebige Zeichenkette und fix ; sei . Es sei ; dann ist . Dann können wir schreibenε > 0 K = = log ( 1 / ε ) ⌋ L K = { y : d ( x , y ) < ε } L K = { y : s ( x , y ) > K $x$$\varepsilon > 0$$K = \lfloor \log(1/\varepsilon) \rfloor$$L_K = \{y : d(x,y) < \varepsilon\}$$L_K = \{y : s(x,y) > K\}$

Aber ist entscheidbar: Bei Eingabe von kann man die ersten Entscheider für und simulieren und nur dann akzeptieren, wenn jeder entweder beide akzeptiert oder beide abgelehnt hat. y K x y $L_K$$y$$K$$x$$y$$~\square$

Jetzt sind wir fast fertig:

Prop. Sei stetig. Wenn rekursiv ist, ist rekursiv.L f - 1 ( L $f$$L$$f^{-1}(L)$

Beweis. Unter einer kontinuierlichen Funktion ist das Vorbild einer Nachbarschaft eine Nachbarschaft.

Interessanterweise denke ich, dass in diesem Raum eine stetige Funktion gleichmäßig stetig ist: Sei stetig, so existiert für jeden Punkt für jedes ein entsprechendes . Repariere ein und lasse . Es gibt eine endliche Anzahl von Kugeln der Größe : es gibt ; dann gibt es ; dann und so weiter. assoziiert mit jeder dieser Sprachenx ε & dgr; ε K = ⌊ log ( 1 / ε ) ⌋ ε L ( T ( T 2 ) ⋯ ∪ $f$$x$$\varepsilon$$\delta$$\varepsilon$$K = \lfloor \log(1/\varepsilon) \rfloor$$\varepsilon$¯ L ( T 1 ) ∪ L ( T 2 ) ⋯ ∪ L ( T K ) L ( T 1 ) ∪ ¯ $L(T_1) \cup L(T_2) \dots \cup L(T_K)$$\overline{L(T_1)} \cup L(T_2) \dots \cup L(T_K)$f L i L ' i δ i x ∈ L ' i d ( x , y ) ≤ δ $L(T_1) \cup \overline{L(T_2)} \dots \cup L(T_K)$$f$$L_i$eine Vorabbildsprache mit zugehörigem Durchmesser . Für jedes , . So können wir das Minimum über dieses endlich viele nehmen s die einheitliche Kontinuität konstant erhalten mit dieser assoziiert .$L_i^{\prime}$$\delta_i$$x \in L_i^{\prime}$epsi ; $d(x,y) \leq \delta_i \implies d(f(x),f(y)) \leq \varepsilon$$\delta$$\delta$$\varepsilon$