Generador de todos los códigos de M.T. existentes

Partimos de las siguientes bases:

* Cualquier lenguaje sobre el alfabeto {0,1} se puede reconocer en una M.T. cuyo alfabeto de cinta sea {0,1,B}

* No hay necesidad de más de un estado final en cualquier M. T.

Sea la Máquina de Turing 

M = ⟨{0, 1}, {q1 , q2 , q3 }, {0, 1, B}, f , q1 , B, {q2 }⟩ 

con 

f(q1 , 1) = (q3 , 0, R) 

f(q3 , 0) = (q1 , 1, R) 

f(q3 , 1) = (q2 , 0, R) 

f(q3 , B) = (q3 , 1, L)

Podemos codificarla de la siguiente manera:

11101001000101001100010101001001100010010010100110001000100010010111 

(Más info en los apuntes 8.2.1) 

Teniendo en cuenta esta codificación descrita y conociendo el alfabeto Σ = {0, 1}, entonces crearemos un generador canónico de 0's y 1's tal que se vayan generando cadenas Σ* =  λ, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011...

Este generador irá sacando números en binario indefinidamente. A las cadenas generadas las hacemos pasar por otra M.T. que nos acepte las cadenas de entrada que se adecuen al formato correcto de una M.T. codificada. Si es correcta, generará la cadena, sino seguirá esperando más cadenas correctas.

Esta segunda M.T. M1 aceptaría cualquier cadena del siguiente lenguaje, 

L(M1) ={x ∈ Σ+ | x = 111(0i10j10k10l10m11)n1 / i,k,n > 0,  0 > j, l <= 3, k > 0,  0 > m <= 2 }

Y el Generador de M.T. sintácticamente correctas (M2) vendría a ser algo parecido a esto:

Donde si w ∈ L(M1) entonces la cadena w es una máquina de turing sintácticamente correcta.

En caso de no pertenecer a L(M1) no se generaría nada.

Por tanto queda demostrado que es posible la construcción de una M.T. capaz de generar todos los códigos de M.T. sintácticamente correctas.

En cuanto al apartado B de la cuestión, la respuesta es 2) Tengo infinitas máquinas, pero va a ser que no tengo bastantes.

Al estar involucrados los números enteros como indices de estados (y el propio generador incorporado), y sabiendo que son infinitos, es lógica esta conclusión. Dado que pueden existir M.T.'s con infinitos estados (infinitos pero contables) y a su vez el generador extrae infinitas cadenas, infinito se nos quedará corto.