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 informáticos" (Minsky, 1967: 200). Con sólo 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 documento, Wang presentó una variedad de máquinas equivalentes, incluida la que llamó la máquina W , que es la máquina B con una instrucción de "borrar" agregada 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 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 marca de impresión de cinta cuadrada escaneada *, vaya 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 de máquina B simple 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 cinta escaneado, borre la marca * (si hay una) y luego vaya 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 Informática) 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 doctores R. Hamming , D. McIlroy y V. Vyssotsky de los laboratorios telefónicos Bell y con el Dr. H. Wang de la Universidad de Oxford".
- Joachim Lambek (1961) recibió el 15 de junio de 1961 How to Program an Infinite Abacus , 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), Computación: Máquinas finitas e infinitas , Prentice-Hall, Inc. Englewood Cliffs, NJ En particular, véase la p. 262ff (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 hay una máquina de Turing equivalente T N que nunca cambia un símbolo escrito una vez . De hecho, construiremos un símbolo de dos símbolos". máquina T N que sólo puede cambiar los cuadrados en blanco de su cinta a unos, pero no puede cambiar un 1 de nuevo a un espacio en blanco ". Minsky luego ofrece una prueba de esto.