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:
Los modelos funcionales incluyen:
Los modelos concurrentes incluyen:
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.