Hispanopedia WikiTal como lo presentó Hao Wang (1954, 1957), su máquina básica B es un modelo computacional extremadamente simple equivalente a la máquina de Turing . Es "la primera formulación de una teoría de la máquina de Turing en términos de modelos similares a los de una computadora" (Minsky, 1967: 200). Con solo 4 instrucciones secuenciales, es muy similar, pero incluso más simple, que las 7 instrucciones secuenciales de la máquina Post-Turing . En el mismo artículo, Wang introdujo una variedad de máquinas equivalentes, incluyendo lo que llamó la máquina W , que es la máquina B con una instrucción de "borrado" añadida al conjunto de instrucciones.
Descripción
Según la definición de Wang (1954), la máquina B tiene a su disposición solo 4 instrucciones: [ 1 ]
- → : Mueva el cabezal de escaneo de cinta un cuadrado de cinta a la derecha (o mueva la cinta un cuadrado a la izquierda), luego continúe con la siguiente instrucción en secuencia numérica;
- ← : Mueva el cabezal de escaneo de cinta un cuadrado de cinta a la izquierda (o mueva la cinta un cuadrado a la derecha), luego continúe con la siguiente instrucción en secuencia numérica;
- * : En la cinta escaneada, imprima la marca cuadrada * y luego pase a la siguiente instrucción en secuencia numérica;
- C n: Transferencia condicional (salto, bifurcación) a la instrucción "n": Si el cuadrado de cinta escaneado está marcado, entonces vaya a la instrucción "n"; de lo contrario (si el cuadrado escaneado está en blanco), continúe con la siguiente instrucción en secuencia numérica.
Un ejemplo de una instrucción simple de máquina B es su ejemplo: [ 2 ]
- 1. *, 2. →, 3. C2, 4. →, 5. ←
Él lo reescribe como una colección de pares ordenados:
- { ( 1, * ), ( 2, → ), ( 3, C2 ), ( 4, → ), ( 5, ← ) }
La máquina W de Wang es simplemente la máquina B con una instrucción adicional.
- 5. E : En la cinta escaneada, borre la marca * (si la hay) y luego pase a la siguiente instrucción en secuencia numérica.
Véase también
Notas
Referencias
- Wang, Hao (1957). «Una variante de la teoría de Turing sobre las máquinas de computación» . Journal of the Association for Computing Machinery . 4 : 63–92 . doi : 10.1145/320856.320867 .
Presentado en la reunión de la Asociación, 23-25 de junio de 1954.
- Melzak, ZA (septiembre de 1961). «Un enfoque aritmético informal de la computabilidad y la computación». Boletín Matemático Canadiense . 4 (3): 279–293 . doi : 10.4153/CMB-1961-031-9 .
Recibido el 15 de mayo de 1961. Melzak no ofrece referencias, pero reconoce «el beneficio de las conversaciones con los Dres. R. Hamming , D. McIlroy y V. Vyssotsky de los Laboratorios Bell Telephone y con el Dr. H. Wang de la Universidad de Oxford».
- Lambek, Joachim (septiembre de 1961). "Cómo programar un ábaco infinito". Boletín Matemático Canadiense . 4 (3): 295– 302. doi : 10.4153/CMB-1961-032-6 .
Recibido el 15 de junio de 1961. El Apéndice II propone una definición formal de "programa"; referencias Melzak (1961) y Kleene (1952) Introducción a la metamatemática .
- Minsky, Marvin Lee (1967). Computación: Máquinas finitas e infinitas . Englewood Cliffs, NJ: Prentice-Hall. págs. 262–264 . ISBN 9780131655638(
pág. 262 y ss., cursiva en el original): Ahora podemos demostrar el hecho notable, demostrado por primera vez por Wang (1957) , de que para cualquier máquina de Turing T existe una máquina de Turing equivalente T N que nunca cambia un símbolo escrito una vez . De hecho, construiremos una máquina de dos símbolos T N que solo puede cambiar los cuadrados en blanco de su cinta por 1, pero no puede cambiar un 1 de nuevo por un espacio en blanco. Minsky luego ofrece una demostración de esto.
- Máquina de Turing