Modelo de computación

En la teoría de la computabilidad y en la teoría de la complejidad computacional, un modelo de computación es la definición un conjunto de operaciones permitibles usadas en el cómputo y sus respectivos costos. Solo asumiendo un cierto modelo de computación es posible analizar los recursos de cómputo requeridos, como el tiempo de ejecución o el espacio de memoria, o discutir las limitaciones de algoritmos o computadores.

Algunos ejemplos de modelos incluyen las máquinas de Turing, las funciones recursivas, cálculo lambda, y sistema de producción.

En la ingeniería dirigida por modelos, el modelo de computación explica cómo el comportamiento del sistema entero es el resultado del comportamiento de cada uno de sus componentes.

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

Hay muchos modelos de computación, diferenciándose en el conjunto de operaciones admisibles y de su costo computacional. Ellos entran en las amplias categorías siguientes:

• La máquina abstracta, usada en pruebas de computabilidad y de los límites superiores en la complejidad computacional de algoritmos, y
• El modelo de árbol de decisión, usado en las pruebas de los límites más bajos en la complejidad computacional de problemas algorítmicos.