Diferencia entre revisiones de «Teoría de la computación»
Contenido eliminado Contenido añadido
Deshecha la edición 39259607 de 189.146.101.75 (disc.) |
|||
Línea 2:
== Principales subramas ==
=== Teoría de autómatas ===
{{ap|Teoría de autómatas}}
Esta teoría provee modelos matemáticos que formalizan el concepto de ''computadora'' o ''algoritmo'' de manera suficientemente simplificada y general para que se puedan analizar sus capacidades y limitaciones. Algunos de estos modelos juegan un papel central en varias aplicaciones de las ciencias de la computación, incluyendo procesamiento de texto, [[compilador]]es, diseño de hardware e [[inteligencia artificial]].
Los tres principales modelos son los '''[[Autómata finito|autómatas finitos]]''', '''[[Autómata con pila|autómatas con pila]]''' y '''[[Máquina de Turing|máquinas de Turing]]''', cada uno con sus variantes [[Algoritmo determinista|deterministas]] y no deterministas. Los autómatas finitos son buenos modelos de computadoras que tienen una cantidad limitada de memoria, los autómatas con pila modelan los que tienen gran cantidad de memoria pero que solo pueden manipularla a manera de [[Pila (informática)|pila]] (el último dato almacenado es el siguiente leído), y las máquinas de Turing modelan las computadoras que tienen una gran cantidad de memoria almacenada en una cinta. Estos autómatas están estrechamente relacionados con la teoría de [[Lenguaje formal|lenguajes formales]]; cada autómata es equivalente a una [[gramática formal]], lo que permite reinterpretar la [[jerarquía de Chomsky]] en términos de autómatas.
Existen muchos otros tipos de autómatas como las [[Máquina de acceso aleatorio|máquinas de acceso aleatorio]], [[Autómata celular|autómatas celulares]], [[Máquina ábaco|máquinas ábaco]] y las [[Máquina de estado abstracto|máquinas de estado abstracto]]; sin embargo en todos los casos se ha mostrado que estos modelos no son más generales que la máquina de Turing, pues la máquina de Turing tiene la capacidad de simular cada uno de estos autómatas. Esto da lugar a que se piense en la máquina de Turing como el modelo universal de computadora.
=== Teoría de la computabilidad ===
| |||