Modelo de cálculo

En informática , y más específicamente en teoría de computabilidad y teoría de complejidad computacional , un modelo de computación es un modelo que describe cómo se calcula la salida de una función matemática dada una entrada. Un modelo describe cómo se organizan las unidades de computación, memorias y comunicaciones. ^[1] La complejidad computacional de un algoritmo se puede medir dado un modelo de computación. El uso de un modelo permite estudiar el rendimiento de los algoritmos independientemente de las variaciones que son específicas de implementaciones particulares y tecnología específica.

Los modelos de computación se pueden clasificar en tres categorías: modelos secuenciales, modelos funcionales y modelos concurrentes.

Los modelos secuenciales incluyen:

• Máquinas de estados finitos
• Máquinas de correos ( máquinas Post–Turing y máquinas de etiquetas ).
• Autómatas de empuje hacia abajo
• Registrar máquinas
  • Máquinas de acceso aleatorio
• Máquinas de Turing
• Modelo de árbol de decisión

Los modelos funcionales incluyen:

• Sistemas de reescritura de resúmenes
• Lógica combinatoria
• Funciones recursivas generales
• Cálculo lambda

Los modelos concurrentes incluyen:

• Modelo de actor
• Autómata celular
• Redes de interacción
• Redes de procesos de Kahn
• Puertas lógicas y circuitos digitales
• Redes de Petri
• Cálculo de procesos
• Flujo de datos sincrónico

Algunos de estos modelos tienen variantes tanto deterministas como no deterministas . Los modelos no deterministas corresponden a límites de ciertas secuencias de computadoras finitas, pero no corresponden a ningún subconjunto de computadoras finitas; ^{[ cita requerida ]} se utilizan en el estudio de la complejidad computacional de algoritmos.

Los modelos difieren en su poder expresivo; por ejemplo, cada función que puede calcularse mediante una máquina de estados finitos también puede calcularse mediante una máquina de Turing , pero no al revés.

En el campo del análisis de algoritmos en tiempo de ejecución , es común especificar un modelo computacional en términos de operaciones primitivas permitidas que tienen un costo unitario, o simplemente operaciones de costo unitario . Un ejemplo comúnmente utilizado es la máquina de acceso aleatorio , que tiene un costo unitario para el acceso de lectura y escritura a todas sus celdas de memoria. En este sentido, se diferencia del modelo de máquina de Turing mencionado anteriormente.

• Máquina de pila (máquina de 0 operandos)
• Máquina acumuladora (máquina de 1 operando)
• Máquina de registro (máquina de 2,3,... operandos)
• Máquina de acceso aleatorio
• Máquina abstracta
• Modelo de sonda celular
• Modelo de consulta de Robertson-Webb
• Jerarquía de Chomsky
• Completitud de Turing

• Fernández, Maribel (2009). Modelos de computación: una introducción a la teoría de la computabilidad . Temas de pregrado en ciencias de la computación. Springer. ISBN 978-1-84882-433-1.
• Savage, John E. (1998). Modelos de computación: exploración del poder de la computación . Addison-Wesley. ISBN 978-0201895391.