Teoria de la computabilidad
Páginas: 2 (442 palabras)
Publicado: 11 de noviembre de 2010
La Teoría de la computabilidad es la parte de la computación que estudia los problemas de decisión que pueden ser resueltos con un algoritmo o equivalentemente con una máquina de Turing. La teoría dela computabilidad se interesa a cuatro preguntas:
• ¿Qué problemas puede resolver una máquina de Turing?
• ¿Qué otros formalismos equivalen a las máquinas de Turing?
• ¿Qué problemasrequieren máquinas más poderosas?
• ¿Qué problemas requieren máquinas menos poderosas?
La teoría de la complejidad computacional clasifica las funciones computables según el uso que hacen dediversos recursos en diversos tipos de máquina.
Antecedentes
El origen de los modelos abstractos de computación se encuadra en los años '30 (antes de que existieran los ordenadores modernos), parael trabajo de los lógicos Alonzo Church, Kurt Gödel, Stephen Kleene, Emil Leon Post, y Alan Turing. Estos trabajos iniciales han tenido una profunda influencia, tanto en el desarrollo teórico como enabundantes aspectos de la práctica de la computación; previendo incluso la existencia de ordenadores de propósito general, la posibilidad de interpretar programas, la dualidad entre software yhardware, y la representación de lenguajes por estructuras formales basados en reglas de producción.
Máquina de Turing (MT) es un modelo computacional que realiza una lectura/escritura de manera automáticasobre una entrada llamada cinta, generando una salida en esta misma.
Este modelo está conformado por un alfabeto de entrada y uno de salida, un símbolo especial llamado blanco(normalmente b, Δ o 0),un conjunto de estados finitos y un conjunto de transiciones entre dichos estados. Su funcionamiento se basa en una función de transición, que recibe un estado inicial y una cadena de caracteres(lacinta, la cual es finita por la izquierda) pertenecientes al alfabeto de entrada. Luego va leyendo una celda de la cinta, borrando el símbolo, escribir el nuevo símbolo perteneciente al alfabeto de...
• ¿Qué problemas puede resolver una máquina de Turing?
• ¿Qué otros formalismos equivalen a las máquinas de Turing?
• ¿Qué problemasrequieren máquinas más poderosas?
• ¿Qué problemas requieren máquinas menos poderosas?
La teoría de la complejidad computacional clasifica las funciones computables según el uso que hacen dediversos recursos en diversos tipos de máquina.
Antecedentes
El origen de los modelos abstractos de computación se encuadra en los años '30 (antes de que existieran los ordenadores modernos), parael trabajo de los lógicos Alonzo Church, Kurt Gödel, Stephen Kleene, Emil Leon Post, y Alan Turing. Estos trabajos iniciales han tenido una profunda influencia, tanto en el desarrollo teórico como enabundantes aspectos de la práctica de la computación; previendo incluso la existencia de ordenadores de propósito general, la posibilidad de interpretar programas, la dualidad entre software yhardware, y la representación de lenguajes por estructuras formales basados en reglas de producción.
Máquina de Turing (MT) es un modelo computacional que realiza una lectura/escritura de manera automáticasobre una entrada llamada cinta, generando una salida en esta misma.
Este modelo está conformado por un alfabeto de entrada y uno de salida, un símbolo especial llamado blanco(normalmente b, Δ o 0),un conjunto de estados finitos y un conjunto de transiciones entre dichos estados. Su funcionamiento se basa en una función de transición, que recibe un estado inicial y una cadena de caracteres(lacinta, la cual es finita por la izquierda) pertenecientes al alfabeto de entrada. Luego va leyendo una celda de la cinta, borrando el símbolo, escribir el nuevo símbolo perteneciente al alfabeto de...
Leer documento completo
Regístrate para leer el documento completo.