# 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.
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.
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.

## Vegeu també

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

## Referències

* ↑ «abstract machine from FOLDOC». [Consulta: 1r gener 2019].
* 1 2 Handbook of theoretical computer science. Amsterdam: Elsevier, 1990. ISBN 0444880755.
Teoria d'autòmats: llenguatge formals i gramàtica formals :
Jerarquia de ChomskyGramàtiquesLlenguatgesMàquines abstractes
Tipus-0
Tipus-1
Tipus-2
Tipus-3
Sense restriccions
(sense nom)
Sensitiva al context
Concatenació de rang
Indexada
Sistema lineal de reescriptura lliure de context
Adjunció d'arbres
Lliure de context
Lliure de context determinista
Visibly pushdown
Regular
No recursives
Enumerable recursivament
Decidible
Sensible al context
Concatenació de rang$^*$
Indexat$^*$
Llenguatge lineal de reescriptura lliure de context
Adjunció d'arbres
Lliure de context
Lliure de context determinista
Visibly pushdown
Regular
Lliure d'estrella
Finit
Màquina de Turing
Decider
Linealment acotat
Màquina de Turing PTIME
Pila anidada
Autòmat per subprocessos
Autòmat amb pila d'arbre restringit
Pila incrustada
Autòmat amb pila no-determinista
Autòmat amb pila determinista
Visibly pushdown
Finit
Sense comptadors(amb monoides finits aperiòdics)
Finit acíclic :
Cada categoria de llenguatges, excepte aquells marcats per $^*$, és un subconjunt de la categoria superior. Qualsevol llenguatge en aquesta categoria es genera per una gramàtica i per un autòmat de la categoria de la mateixa línia. :