En informática , y más específicamente en teoría de la computabilidad y teoría de la 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 cálculos, memorias y comunicaciones. [1] La complejidad computacional de un algoritmo se puede medir dado un modelo de cálculo. El uso de un modelo permite estudiar el desempeño 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:
Los modelos funcionales incluyen:
Los modelos concurrentes incluyen:
Algunos de estos modelos tienen variantes tanto deterministas como no deterministas . Los modelos no deterministas no son útiles para el cálculo práctico; [ cita necesaria ] se utilizan en el estudio de la complejidad computacional de los algoritmos.
Los modelos se diferencian por 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 en tiempo de ejecución de algoritmos , es común especificar un modelo computacional en términos de operaciones primitivas permitidas que tienen 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.