Tal 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, a las 7 instrucciones secuenciales de la máquina Post-Turing . En el mismo artículo, Wang presentó una variedad de máquinas equivalentes, incluida la que llamó máquina W , que es la máquina B con una instrucción de "borrado" agregada al conjunto de instrucciones.
Descripción
Según la definición de Wang (1954), la máquina B tiene a su disposición sólo 4 instrucciones:
- (1) → : Mueva el cabezal de escaneo de cinta un cuadrado de cinta hacia la derecha (o mueva la cinta un cuadrado hacia la izquierda), luego continúe con la siguiente instrucción en secuencia numérica;
- (2) ← : Mueva el cabezal de escaneo de cinta un cuadrado hacia la izquierda (o mueva la cinta un cuadrado hacia la derecha), luego continúe con la siguiente instrucción en secuencia numérica;
- (3) * : En la cinta escaneada, imprima la marca cuadrada * y luego pase a la siguiente instrucción en secuencia numérica;
- (4) C n: "Transferencia" condicional (salto, bifurcación) a la instrucción "n": si el cuadrado de cinta escaneado está marcado, 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 una máquina B es su ejemplo (p. 65):
- 1. *, 2. →, 3. C2, 4. →, 5. ←
Reescribe esto 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 el cuadrado de la cinta escaneada, borre la marca * (si la hay) y luego pase a la siguiente instrucción en secuencia numérica.
Ver también
Referencias
- Hao Wang (1957), Una variante de la teoría de las máquinas informáticas de Turing , JACM (Revista de la Asociación de Maquinaria de Computación) 4; 63–92. Presentado en la reunión de la Asociación del 23 al 25 de junio de 1954.
- ZA Melzak (1961) recibió el 15 de mayo de 1961 An Informal Arithmetical Approach to Computability and Computation , Canadian Mathematical Bulletin , vol. 4, núm. 3. Septiembre de 1961, páginas 279–293. Melzak no ofrece referencias pero reconoce "el beneficio de las conversaciones con los Drs. R. Hamming , D. McIlroy y V. Vyssotsky de Bell Telephone Laborators y con el Dr. H. Wang de la Universidad de Oxford".
- Joachim Lambek (1961) recibió el 15 de junio de 1961 Cómo programar un ábaco infinito , Mathematical Bulletin, vol. 4, núm. 3. Septiembre de 1961, páginas 295–302. En su Apéndice II, Lambek propone una "definición formal de 'programa'". Hace referencia a Melzak (1961) y Kleene (1952) Introducción a las metamatemáticas .
- Marvin Minsky (1967), Computación: Máquinas finitas e infinitas , Prentice-Hall, Inc. Englewood Cliffs, Nueva Jersey En particular, consulte la p. 262 y siguientes (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. máquina T N que sólo puede cambiar los cuadrados en blanco de su cinta a 1, pero no puede volver a convertir un 1 en un espacio en blanco". Minsky ofrece entonces una prueba de ello.
