El método de permiso

Question

Definir el término permiso tardío de la siguiente manera: $C$ permisos tardíos un elemento $x$ para entrar $A_{s+1}$ si para una función computable fija $f$ con $f(n)>n$ existe $y \leq x$ de tal manera que $y \in C_{f(s)}-C_{s}$ . En otras palabras, $C$ permisos $x$ para entrar $A$ pero puede tardar un poco en dar su permiso.

Supongamos que $C$ tarde permite que cada elemento de $A$ para alguna enumeración de $A$ y alguna función computable $f$ . Entonces, ¿cómo puedo probar que $$A \leq_ {T}C$$

Además, necesito mostrar que hay alguna otra enumeración $\{A_{s}^{*}\}$ de $A$ de tal manera que $C$ permisos sobre $A$ de la manera habitual: es decir, si $x \in A_{s+1}^{*}-A_{s}^{*}$ entonces existe $y \leq x$ de tal manera que $y \in C_{s+1}-C_{s}$ . Esto significa que el permiso tardío no nos da nada que el permiso normal no pueda dar.

---

Definiciones y anotaciones:

$A \leq_ {T}C$ significa $A$ es Turing reducible a $C$

Teorema relevante: Para cualquier conjunto de c.e. no computable $C$ hay un conjunto simple $A \leq_ {T}C$ .

$( \exists y \leq x)[y \in C_{s+1}-C_{s}]$ es decir.., $C$ permisos $x$ en el estado $s+1$

Answer 1

Por enumeración, asumo que siempre te refieres a la enumeración computable.

Supongamos que $C$ "permisos tardíos" $A$ . Deje que $A_s$ ser una enumeración computable de $A$ , $C_s$ ser una enumeración de $C$ y $f$ ser una función computable que satisfaga la definición de "permiso tardío".

Para mostrar $A \leq_T C$ uno quiere mostrar que dado un oráculo para $C$ se puede calcular la relación de pertenencia $x \in A$ . Con el oráculo para $C$ puedes encontrar todos los $y \leq x$ de tal manera que $y \in C$ . Supongamos que $y_1, ..., y_n$ son todos los $y$ es con esta propiedad. Ya que cada uno $y_i \in C$ existe una más pequeña $t_i$ de tal manera que $y_i \in C_{t_i}$ .

Finalmente $x \in A$ si y sólo si existe una $1 \leq i \leq n$ de tal manera que existe una $s < t_i$ de tal manera que $y_i \in C_{f(s)}$

Se ha demostrado que $A \leq_T C$ .

Asumiré que las enumeraciones computables permiten la entrada de más de un elemento en cualquier etapa. Otra convención usual es que en cualquier etapa, si $x \in A_s$ Entonces $x \leq s$ .

Definir una enumeración computable $A_s^*$ de la siguiente manera:

$A_0^* = \emptyset $

$x \in A^*_{s + 1}$ si y sólo si $x \leq s$ y existe un $t \leq s$ de tal manera que existe una $y \leq x$ de tal manera que $y \in C_{f(t)} - C_t$ y el menos $u$ de tal manera que $t \leq u < f(t)$ y $y \in C_{u + 1} - C_u$ es menor que $s$ .

---

Tal vez un poco más fácil de entender:

$A_0^* = \emptyset $

$x \in A^*_{s + 1}$ si y sólo si $x \in A_s^*$ o $x \leq s$ y existe un $t \leq s$ de tal manera que existe una $y \leq x$ de tal manera que $y \in C_{f(t)} - C_t$ y el menos $u$ de tal manera que $t \leq u < f(t)$ y $y \in C_{u + 1} - C_u$ es $s$ .

---

Está claro que $A_s^*$ es computable. $A_{s}^* \subseteq A_{s+1}^*$ . Por definición, si $x \in A_{s + 1}^* - A_s^*$ Entonces $x \in C_{s + 1} - C_s$ . Para mostrar que esta nueva enumeración realmente enumera todos los $A$ . Supongamos que $a \in A$ . Entonces existe un $v$ de tal manera que (en la enumeración original), $x$ entra en $A_{v + 1} - A_v$ . Esto significa que hay algunos $y < x$ de tal manera que $y \in C_{f(v)} - C_v$ . Existe un mínimo $u$ entre $v$ y $f(v)$ de tal manera que $y \in C_{u + 1} - C_u$ . Luego $x \in A_u^*$ .

$A_s^*$ es una enumeración computable de $A$ que permite en el sentido usual con respecto a la enumeración de $C$ .