Интересное метрическое пространство, связанное с машинами Тьюринга

В этом вопросе мы рассматриваем только машины Тьюринга, которые останавливаются на всех входах. Если $k \in \mathbb{N}$ то через $T_k$ мы обозначаем машину Тьюринга, код которой равен $k$ .

Рассмотрим следующую функцию

Другими словами, - это код самой маленькой машины Тьюринга, которая точно распознает одну из строкТеперь мы можем определить следующую картуx , y $s(x,y)$$x,y.$

Можно быстро проверить, что $d(x,y)$ индуцирует метрическое пространство (фактически ультраметрию) на $\Sigma^{*}.$

Теперь я хотел бы доказать, что если $f:\Sigma^{*} \mapsto \Sigma^{*}$ является равномерно непрерывной функцией, то для любого рекурсивного языка L $f^{-1}(L)$ рекурсивна.

Другими словами, пусть $f$ будет картой такой, что для каждого $\epsilon > 0$ найдется $\delta > 0$ такая, что если для строк $x,y \in \Sigma^{*}$

Теперь, как уже отмечалось в этом посте, один из способов решения этой проблемы состоит в том, чтобы показать, что существует машина Тьюринга, которая задает строку вычисляющую$x \in \Sigma^{*}$$f(x).$

Я застрял, доказывая это утверждение, и медленно размышляю, есть ли какой-то другой подход для решения этой проблемы?

Советы, предложения и решения приветствуются!

Редактировать: убрал подсказки, выложил моё решение.

Вот мое решение. Мы собираемся выбрать опорную точку где f ( x ) ∈ L, и рассмотрим вселенную с точки зрения x и f ( x ) . Оказывается, что каждая «окрестность» точки соответствует рекурсивному языку. Таким образом, L - это окрестность вокруг f ( x ) , и вокруг x будет некоторая окрестность, которая будет отображаться в ней; эта окрестность - рекурсивный язык.$x$$f(x) \in L$$x$$f(x)$$L$$f(x)$$x$

Лемма. В этом пространстве язык рекурсивен тогда и только тогда, когда он является окрестностью каждой из его строк.

Доказательство . Во- первых, исправить рекурсивный язык , и пусть х ∈ L . Пусть K минимальный индекс решающего для L . Тогда мы имеем , что если у ∉ л , ев ( х , у ) ≤ K , так что д ( х , у ) ≥ 1 / 2 К . Таким образом , d ( х , у ) < 1 / 2 К означает , что у $L$$x \in L$$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$

Во-вторых, пусть - произвольная строка и зафиксируем ε > 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\}$

Но разрешима: на входе y можно смоделировать первые K решателей по x и y и принять, если и только если каждый либо принял оба, либо отклонил оба. $L_K$$y$$K$$x$$y$$~\square$

Теперь мы почти закончили:

Опора. Пусть непрерывно. Если L рекурсивно, то f - 1 ( L ) рекурсивно.$f$$L$$f^{-1}(L)$

Доказательство. Под непрерывной функцией прообраз окрестности есть окрестность.

Интересно, что я думаю, что в этом пространстве непрерывная функция равномерно непрерывна: пусть непрерывна, поэтому для каждой точки x для каждого ε существует соответствующее δ . Зафиксируем ε и пусть K = ⌊ log ( 1 / ε ) ⌋ . Существует конечное число шариков размера ε : существует L ( T 1 ) ∪ L ( T 2 ) ⋯ ∪ L ( T K ) ; тогда есть$f$$x$$\varepsilon$$\delta$$\varepsilon$$K = \lfloor \log(1/\varepsilon) \rfloor$$\varepsilon$$L(T_1) \cup L(T_2) \dots \cup L(T_K)$; тоL(Т1)∪ ¯ л ( Т 2 ) ⋯∪L(ТК), и так далее. fассоциирует с каждым из этих языковLiязык прообразаL ' i с соответствующим диаметромδi. За каждый$\overline{L(T_1)} \cup L(T_2) \dots \cup L(T_K)$$L(T_1) \cup \overline{L(T_2)} \dots \cup L(T_K)$$f$$L_i$$L_i^{\prime}$$\delta_i$ , d ( x , y ) ≤ δ $x \in L_i^{\prime}$ . Таким образом, мы можем взять минимум над этим конечным числом δ s, чтобы получить равномерную постоянную непрерывности δ, связанную с этим ε .$d(x,y) \leq \delta_i \implies d(f(x),f(y)) \leq \varepsilon$$\delta$$\delta$$\varepsilon$