La computación es mucho más que aritmética. Un modelo de computación debería poder capturar cualquier algoritmo imaginable.
El modelo de máquina de Turing es conceptualmente similar a la arquitectura de la computadora que ahora llamamos la arquitectura von Neumann. Esto no es casualidad; Turing y von Neumann eran contemporáneos y von Neumann sabía del trabajo de Turing (ambos hombres eran matemáticos conocidos).
Una computadora von Neumann tiene una unidad de procesamiento finito que puede leer y escribir en ubicaciones arbitrarias en la tienda de la máquina. El comportamiento de la máquina se describe como un programa finito.
- ¿Cuáles son los desarrollos recientes en tecnología informática?
- ¿Qué software usan los laboratorios de ciencias para ayudar con la investigación?
- ¿Hay alguna idea en criptografía inspirada en la biología?
- ¿Qué podría mejorarse sobre la educación en informática?
- En el campo de la visión por computadora, ¿a qué se refiere el término 'segmentación'?
Una máquina de Turing tiene un control finito que puede leer y escribir en celdas arbitrarias en una cinta infinita. El comportamiento de la máquina de Turing se describe mediante una función de transición finita.
Observe cuán estrechamente corresponden estas dos nociones de cálculo.
Se puede ver que otros modelos de computación imponen restricciones al modelo de máquina de Turing: un autómata de estado finito puede considerarse como una máquina cuya cinta es de solo lectura y de tal manera que cada celda puede leerse como máximo una vez. Un autómata pushdown puede considerarse como una máquina cuya cinta solo se puede leer y escribir desde un extremo (es decir, la cinta se comporta como una pila).
