Màquina abstracta

En teoria de la complexitat computacional, una màquina abstracta és un model teòric d'un computador usat en teoria d'autòmats. L'abstracció de processos computacionals s'usa en les disciplines de les ciències de la computació i en enginyeria informàtica i normalment s'assumeix el paradigma de temps discret.^[1][2]

En teoria de la complexitat, les màquines abstractes normalment s'usen com experiments mentals sobre computabilitat o per analitzar la complexitat d'algorismes. Una màquina abstracta típica consisteix en una definició en termes d'entrada, sortida i un conjunt d'operacions permeses per transformar les entrades en sortides. L'exemple més famós és la màquina de Turing.^[2]

Els tipus abstracte de dades es poden definir en termes de màquines abstractes i les seves operacions semàntiques. Per exemple, un pila (stack) es pot especificada en termes d'operacions d'una màquina abstracta amb una memòria. Amb l'ús de màquines abstractes és possible calcular la quantitat de recursos (temps, memòria, etc.) necessaris per realitzar una operació en particular sense haver de construir el sistema físic.

Hi ha definicions més complexes que creen màquines abstractes amb un conjunt d'instruccions, registres i models de memòria. Un model popular i similar als ordinadors moderns és la màquina RAM, que permet accés aleatori a adreces de memòria. Com que el rendiment varia segons els diferents nivells de memòria cau, models sensibles a les memòries cau i models com el de l'algorisme de memòria cau aliena van adquirint molta importància.

Una màquina abstracta també pot ser el model d'un disseny d'un microprocessador que encara no s'hagi implementat en maquinari. Una màquina abstracta implementada com un simulador per programari s'anomena una màquina virtual.

• Abstracció
• Autòmat finit
• Taxonomia de Flynn
• Espai d'estats