Propiedades de las funciones computables
Índice
Fecha de entrega:
Recordatorio
- Fijamos una numeración efectiva de todas las máquinas de Turing, \(\{\phi_{n} : n \in \N\}\). Abusando un poco de la notación, con \(\phi_{n}\) a veces queremos decir la \(n\)-ésima máquina de Turing y a veces queremos decir la correspondiente función parcial computable \(\phi_{n} : \N \to \N\).
- Fijamos una biyección \(\langle\cdot,\cdot\rangle : \N \times \N \to \N\).
- Existe una máquina de Turing universal; ésta corresponde a función computable \(U : \N \to \N\) tal que \(U(\langle n, x\rangle) = \phi_{n}(x)\).
- El (caso más simple del) teorema s-m-n dice que existe una función total computable \(s_{1}^{1} : \N \times \N \to \N\) tal que para toda \(n, x, y \in \N\) tenemos \(\phi_{n}(\langle x, y \rangle) = \phi_{s_1^1(n,x)}(y)\).
- El teorema del punto fijo dice que si \(f : \N \to \N\) es una función total computable, entonces existe \(n\) tal que las máquinas \(\phi_{n}\) y \(\phi_{f(n)}\) calculan la misma función.
- Un subconjunto \(A \subset \N\) es decidible si es computable su función característica \(\chi_{A} : \N \to \N\), dada por \[\chi_{A}(n) = \begin{cases} 1 & \text{si } n \in A\\ 0 & \text{ si no.}\end{cases}\]
Problemas
Cuando discutimos el problema del paro la función que argumentamos no podía ser computable era: \[\mathsf{paro}(\langle e, x \rangle) = \begin{cases} 1 & \text{si } \phi_{e} \text{ para con entrada } x\\ 0 & \text{si no}\end{cases}\]
Pero varias usamos que no es computable la siguiente función relacionada: \[\mathsf{paro}^\emptyset(e) = \begin{cases} 1 & \text{si } \phi_{e} \text{ para con la cinta en blanco}\\ 0 & \text{si no}\end{cases}\]
Suponiendo que \(\mathsf{paro}\) no es computable, explica por qué \(\mathsf{paro}^\emptyset\) tampoco lo es.
- Prueba que hay una función computable \(f : \N \to \N\) tal que \(\phi_{f(x)}(y) = 2\phi_{x}(y)\) para toda \(x, y \in \N\).
- Prueba que la hipótesis de que \(f\) es total es necesaria en el teorema del punto fijo.
Prueba esta versión mejorada del teorema del punto fijo:
Si \(f : \N \to \N\) es una función total computable y \(n_{0}\) es cualquier número natural, entonces existe \(n > n_{0}\) tal que las máquinas \(\phi_{n}\) y \(\phi_{f(n)}\) calculan la misma función.
- Enuncia con cuidado y demuestra el teorema de Rice, que informalmente dice que cualquier propiedad semántica no trivial de máquinas de Turing es indecidible. (Exactamente qué dice el enunciado formal del teorema, particularmente qué significa «propiedad semántica», es un poco sutil y escribirlo bien es una parte importante del ejercicio).
- Demuestra que es indecidible si dos funciones computables terminan para las mismas entradas, o más formalmente, prueba que el conjunto \(\{\langle m, n \rangle : \dom(\phi_{m}) = \dom(\phi_{n})\} \subset \N\) es indecidible.
Demuestra que las siguientes son equivalentes para \(x \in \mathbb{R}\):
- existe una \(f : \N \to \mathbb{Q}\) total computable tal que \(|x-f(n)| <\frac{1}{n}\) para toda \(n>1\),
- existe una \(g : \N \to \mathbb{Q}\) total computable tal que \(|x-g(n)| <\frac{1}{2^{n}}\) para toda \(n \in \N\), y
- existe una \(h : \N \to \mathbb{Z}\) total computable tal que \(|x-\frac{h(n)}{n}| <\frac{1}{n}\) para toda \(n >1\).
(La primera es la que usamos como definición de número real computable en clase).
- Un subconjunto \(A \subset \N\) se llama semidecidible si existe una
function parcial computable \(f : \N \to \N\) tal que:
- \(A \subset \dom(f)\),
- para todo \(a \in A\), \(f(a) = 1\); y
si \(b \in \mathsf{dom}(f)\) pero \(b \notin A\), entonces \(f(b)=0\).
Prueba que \(A\) es semidecidible si y solo si existe una función parcial computable \(g : \N \to \N\) con \(\dom(g) = A\).
- Prueba que si \(A\) y \(B\) son semidecidibles (ver el problema anterior) entonces \(A \cup B\) y \(A \cap B\) también lo son.
- Da un ejemplo de un conjunto que sea semidecidible pero no decidible.