Teoria de la computació: diferència entre les revisions
Contingut suprimit Contingut afegit
m Plantilles |
m Diacrítics |
||
Línia 13:
Els tres principals models són els [[Autòmat finit|autòmats finits]] , [[Autòmat amb pila|autòmats amb pila]] i [[Màquina de Turing|màquines de Turing]] , cadascun amb les seves variants [[Algorisme determinista|deterministes]] i no deterministes. Els autòmats finits són bons models d'ordinadors que tenen una quantitat limitada de memòria, els autòmats amb pila modelen els que tenen gran quantitat de memòria però que només poden manipular a manera d'[[Pila (informàtica)|pila]] (l'última dada emmagatzemat és el següent llegit), i les màquines de Turing modelen les computadores que tenen una gran quantitat de memòria emmagatzemada en una cinta. Aquests autòmats estan estretament relacionats amb la teoria de [[Llenguatge formal|llenguatges formals]], cada autòmat és equivalent a una [[gramàtica formal]], el que permet reinterpretar la [[jerarquia de Chomsky]] en termes d'autòmats.
Existeixen molts altres tipus d'autòmats com les [[Màquina d'accés aleatori|màquines d'accés aleatori]], [[Autòmat cel lular|autòmats cel·lulars]], [[Màquina àbac|màquines àbac]] i les [[Màquina d'estat abstracte|màquines d'estat abstracte]], però en tots els casos s'ha mostrat que aquests models no són més generals que la [[màquina de Turing]], ja que la màquina de Turing té la capacitat de simular cada un d'aquests autòmats. Això
=== Teoria de la computabilitat ===
| |||