Sí, es posible que una máquina de Turing tome otra máquina de Turing como entrada. Para entender cómo, veamos primero la definición formal de una máquina de Turing. Una máquina de Turing [matemática] M [/ matemática] puede representarse como una 7-tupla [matemática] (Q, \ Sigma, \ Gamma, \ delta, q_0, q_ {aceptar}, q_ {rechazar}) [/ matemática] y biject el conjunto de todas las máquinas de Turing con números naturales.
(si desea que le explique algunas partes de manera más elaborada o no entienda cierta terminología, siéntase libre de preguntarme en los comentarios y editaré mi respuesta en consecuencia).
[matemática] Q [/ matemática] es el conjunto finito de todos los estados, [matemática] \ Sigma [/ matemática] es el conjunto finito del alfabeto de entrada permitido, [matemática] \ Gamma [/ matemática] es el alfabeto de cinta finita (el conjunto de alfabetos posibles que la máquina de Turing puede escribir en una cinta), [math] \ delta [/ math] es una función de transición de [math] (Q \ times \ Gamma) [/ math] a [math] (Q \ times \ Gamma \ times \ {L, R \}) [/ math], [math] q_0 [/ math] es el estado inicial, [math] q_ {accept} [/ math] es el estado de aceptación y [math] q_ {rechazar} [/ math] es el estado de rechazo. Y cada uno de estos conjuntos no es vacío. En particular, los conjuntos [matemática] Q [/ matemática], [matemática] \ Sigma [/ matemática] y [matemática] \ Gamma [/ matemática] son finitos, y por lo tanto la función [matemática] \ delta [/ matemática], siendo uno con un dominio y rango finitos, puede representarse como un conjunto finito [matemática] \ {(x, \ delta (x)): x \ in (Q \ times \ Gamma) \} [/ math]. Llamemos a este conjunto [math] \ Delta [/ math].
- ¿Cuáles son algunas formas interesantes de usar tecnologías no convencionales en la programación?
- Si quiero estar en análisis predictivo y no soy experto en matemáticas ni en programación, ¿cuál debo comenzar a perfeccionar primero y por qué?
- ¿Qué matemática se requiere para entender el cálculo lambda?
- ¿Cuál es la razón por la cual las instalaciones no cambian su esquema de cifrado, de modo que cuando se publique una prueba de P = NP no se verán afectados?
- Cómo usar Excel para encontrar la mediana sin usar una función
Para algunos números naturales [matemática] n [/ matemática], solo hay muchas Máquinas de Turing con [matemática] \ mid Q \ mid + \ mid \ Gamma \ mid + \ mid \ Sigma \ mid + \ mid \ Delta \ mid = n [/ matemática] que son por pares no isomórficos. Podemos enumerar todas las máquinas de Turing que satisfacen esta condición para [matemáticas] n = 1 [/ matemáticas], seguidas de una lista para [matemáticas] n = 2 [/ matemáticas] y así sucesivamente, y anexar estas listas juntas. Representa la máquina de Turing [matemática] m [/ matemática] en esta lista por el número natural [matemática] m [/ matemática]. Como podemos ordenar el conjunto de todas las Máquinas de Turing de manera que cada una de ellas esté representada por un número natural [matemático] m [/ matemático], existe una biyección entre el conjunto de Máquinas de Turing y los números naturales.
Ahora, analicemos [math] \ Sigma [/ math], el conjunto de todos los alfabetos de entrada. Esto es exactamente isomorfo al conjunto de todos los dígitos base- [matemática] \ Sigma [/ matemática]. Por ejemplo, [math] \ {a, b, c \} [/ math] es isomorfo a [math] \ {0,1,2 \} [/ math]. Y cualquier número natural puede representarse en cualquier base que no sea cero. Del isomorfismo se deduce que cualquier número natural puede ser representado por caracteres en [math] \ Sigma [/ math]. Dado que cualquier máquina de Turing puede codificarse como un número natural y cualquier número natural puede ingresarse en su máquina de Turing, puede ingresar una máquina de Turing en otra máquina de Turing.
