Viquipèdia

Teoria de la computació: diferència entre les revisions

Exploració interactiva de l'historial
← Edició anteriorEdició següent →
Contingut suprimit Contingut afegit
VisualWikitext
m Bot prepara format de cometes per a posterior revisió tipogràfica.
m Espais
Línia 28:
Aquesta teoria proveeix models matemàtics que formalitzen el concepte d'ordinador o algorisme de manera prou simplificada i general perquè es puguin analitzar les seves capacitats i limitacions.<ref>{{ref-web |url=https://cs.stanford.edu/people/eroberts/courses/soco/projects/2004-05/automata-theory/basics.html |consulta=15 octubre 2021 |títol=Basics of Automata Theory |editor=Stanford Computer Science |llengua=anglès}}</ref> Alguns d'aquests models tenen un paper central en diverses aplicacions de les ciències de la computació, incloent processament de text, [[compilador]] és, disseny de maquinari i [[intel·ligència artificial]].
 
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]], [[àbac]]s 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ò dona lloc a que es pensi en la màquina de Turing com el model universal d'ordinador.
Obtingut de «https://ca.wikipedia.org/wiki/Teoria_de_la_computació»