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 las computadoras" (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 presentó una variedad de máquinas equivalentes, incluida lo que llamó la 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 cuatro instrucciones:
- (1) → : Mueva el cabezal de escaneo de cinta un cuadrado 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 de cinta 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 * 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, 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 una máquina B es su ejemplo (p. 65):
- 1. *, 2. →, 3. C2, 4. →, 5. ←
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 cuadrada escaneada borre la marca * (si hay una) y luego pase a la siguiente instrucción en secuencia numérica.
Véase también
Referencias
- Hao Wang (1957), Una variante de la teoría de Turing sobre las máquinas de computación , JACM (Revista de la Asociación de Maquinaria de Computación) 4; 63–92. Presentado en la reunión de la Asociación, 23–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, no. 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 los Laboratorios Bell Telephone 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, no. 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), Computation: Finite and Infinite Machines , Prentice-Hall, Inc. Englewood Cliffs, NJ En particular, véase la página 262 y siguientes (cursiva en el original):
- "Ahora podemos demostrar el hecho notable, mostrado 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 sólo puede cambiar casillas en blanco en su cinta a 1, pero no puede convertir un 1 nuevamente a un espacio en blanco". Minsky ofrece luego una prueba de esto.
