Teoria computacional

1308 palabras 6 páginas
Teoría de la computación
La teoría de la computación es una rama de la matemática y la computación que centra su interés en las limitaciones y capacidades fundamentales de las computadoras. Específicamente esta teoría busca modelos matemáticos que formalizan el concepto de hacer un cómputo (cuenta o cálculo) y la clasificación de problemas

Historia

La teoría de la computación comienza propiamente a principios del siglo XX, poco antes que las computadoras electrónicas fuesen inventadas. En esta época varios matemáticos se preguntaban si existía un método universal para resolver todos los problemas matemáticos. Para ello debían desarrollar la noción precisa de método para resolver problemas, es decir, la definición formal de
…ver más…
Los problemas se clasifican en esta teoría de acuerdo a su grado de imposibilidad: • Los computables son aquellos para los cuales sí existe un algoritmo que siempre los resuelve cuando hay una solución y además es capaz de distinguir los casos que no la tienen. También se les conoce como decidibles, resolubles o recursivos. • Los semicomputables son aquellos para los cuales hay un algoritmo que es capaz encontrar una solución si es que existe, pero ningún algoritmo que determine cuando la solución no existe (en cuyo caso el algoritmo para encontrar la solución entraría a un bucle infinito). El ejemplo clásico por excelencia es el problema de la parada. A estos problemas también se les conoce como listables, recursivamente enumerables o reconocibles, porque si se enlistan todos los casos posibles del problema, es posible reconocer a aquellos que sí tienen solución. • Los incomputables son aquellos para los cuales no hay ningún algoritmo que los pueda resolver, no importando que tengan o no solución. El ejemplo clásico por excelencia es el problema de la implicación lógica, que consiste en determinar cuándo una proposición lógica es un teorema; para este problema no hay ningún algoritmo que en todos los casos pueda distinguir si una proposición o su negación es un teorema.
Hay una versión más general de esta clasificación,

Documentos relacionados

  • Tecnología computacional
    1488 palabras | 6 páginas
  • GUIA EGEL INGENIERIA COMPUTACIONAL 2015
    14507 palabras | 58 páginas
  • Pensamiento computacional
    2581 palabras | 11 páginas
  • Teoria computacional de la mente
    20581 palabras | 83 páginas
  • Contextualizacion historica de la teoria computacional de la mente
    3299 palabras | 14 páginas
  • Diferencia entre inteligencia artificial e inteligencia computacional
    880 palabras | 4 páginas
  • Higiene Computacional
    2130 palabras | 9 páginas
  • Linea de tiempo, historia de la teoría computacional de la mente
    1137 palabras | 5 páginas
  • Informe Sistema Computacional Y Sistema Operativo Windows 7
    629 palabras | 3 páginas
  • DELITOS INFORMATICOS Y TERRORISMO COMPUTACIONAL
    2154 palabras | 9 páginas