Alan Turing Empezó Por Definir Lo Que Era Un Número Computable


Alan Turing empezó por definir lo que era un número computable: números reales cuya expresión como decimal puede calcularse por medios finitos.
A partir de esta definición, Turing ideó una máquinaimaginaria que pudiera tratar con números computables. Las características son las siguientes:
Alberga un número finito de condiciones, a las que llamó configuraciones-m ().
La máquina tiene una cintadividida en celdas, cada una de los cuales puede tener escrito un símbolo. La cinta pasa a través de la máquina y tiene una longitud infinita.
En cada momento de funcionamiento de la máquina, unasola celda de la cinta estará dentro de ella.
A la celda de la cinta que puede leer la máquina, le llamaremos la celda activa. El símbolo dentro de esta celda es el único dato de entrada que conoce lamáquina en un momento dado, pero a través de cambios de configuraciones, se puede tener conocimiento de los símbolos leídos anteriormente.
La configuración-m activa en la máquina, junto al símbolo de lacelda activa, forman la configuración de la máquina en un momento dado.
Turing definió también las posibles acciones que podía realizar la máquina:
Escribir un símbolo en la celda activa (P).
Borrarsímbolo de la celda activa (E).
Mover la cinta una posición hacia la izquierda (L).
Mover la cinta una posición hacia la derecha (R).
Finalmente, en cada paso puede producirse un cambio en laconfiguración.
Una máquina de Turing con una sola cinta puede ser definida como una 7-tupla M={Q,Σ,Γ,s,b,F,δ}, donde:

• Q es un conjunto finito de estados.

• Σ es un conjunto finito de símbolos distinto delespacio en blanco, denominado alfabeto de máquina o de entrada.

• Γ es un conjunto finito de símbolos de cinta, denominado alfabeto de cinta. Σ⊆Γ

• s ∈ Q es el estado inicial.

• b ∈ Γ es unsímbolo denominado blanco, y es el único símbolo que se puede repetir un número infinito de veces.

• F⊆Q es el conjunto de estados finales de aceptación.

• δ:Q x Γ → Q x Γ x{L,R} es una función...