¿Es la lengua $\{i|f(i)=1\}$ recursivo, función $f$ se describe más adelante.

Question

Posible duplicado:
Mostrar $f$ es recursivo primitivo, donde $f(n) = 1$ si la expansión decimal de $\pi$ contiene $n$ consecutivos $5$ 's

$$L = \{i\mid f(i)=1\}$$ $f(i)$ es igual a $1$ si existe una secuencia de al menos $i$ consecutivo $5$ s en la expansión decimal de $\pi$ y $0$ de lo contrario.

¿Existe una máquina de Turing total que pueda representar ese lenguaje para cualquier $i$ ?

Answer 1

Como esto son deberes, me limitaré a soltar pistas:

• Si hay una racha de $n$ cincos en $\langle\pi\rangle$ la expansión decimal de $\pi$ también hay carreras de $1,2,\ldots,n-1$ cincos.
• No conocemos la secuencia completa de dígitos en $\langle\pi\rangle$ . Pero hay dos casos a considerar: O bien $\langle\pi\rangle$ tiene recorridos ilimitados de cincos, o no los tiene, y el recorrido máximo tiene longitud $n$ . (no sabemos con precisión cuál es el caso). ¿Puedes idear un decididor (una TM que decida sí o no para cada entrada) para cada caso?