Ensayo: tesis de church-turing y la no computabilidad

879 palabras 4 páginas
Ensayo:” Tesis de Church-Turing y la No Computabilidad”

Al hablar sobre la tesis de Church-Turing y no Computabilidad nos referimos a la parte de la computación llamada Teoría de la Computabilidad, que estudia los problemas de decisión que pueden ser resueltos con un algoritmo (o su equivalente, una maquina de Turing). Esta teoría inicio con los trabajos de Hilbert en 1928, cuya intensión era crear un modelo matemático formal, completo y consistente, en el que a través de un algoritmo, se pudiese determinar la veracidad o falsedad de cualquier proposición formal, al cual se le llamo “problema de decisión”. Si Hilbert hubiera cumplido su objetivo significaría que cualquier problema bien definido se resolvería simplemente al ejecutar
…ver más…
La evidencia de su verdad es abundante pero no definitiva. Precisamente la tesis de Church establece que la definición de algoritmo o procedimiento efectivo es una máquina de Turing. Se ha acordado que un procedimiento efectivo o algoritmo consiste en un número finito y preciso de pasos descrito en un número finito de símbolos que podría ser también ejecutado por un ser humano. En general, la ejecución de un algoritmo no requiere de mayor inteligencia que la necesaria para entender y seguir las instrucciones (incluso sólo seguir).
Un concepto incrustado dentro de la tesis de Church-Turing, es la decibilidad cuya definición nos dice que un problema es decidible si existe un algoritmo que lo resuelva en un tiempo y espacio finito, para los problemas que cumplan este criterio se dicen que son Turing-computables y el identificarlos nos indica los limites y alcances de la computabilidad. Aquellos algoritmos que no cumplen el criterio se llaman no computables (problemas indecidibles) y se definen como todos aquellos que no pueden ser resueltos con un algoritmo aún si se dispone de espacio y tiempo ilimitado. Algunos ejemplos de problemas no computables son:
* El problema de decisión de Hilbert. Que definido de forma diferente, dada una frase del cálculo de predicados de primer orden, decidir si ella es…

Documentos relacionados

  • La maquina de turing
    2520 palabras | 11 páginas
  • Ensayo De La Computadora
    1255 palabras | 6 páginas
  • Ensayo Mantenimiento De Computadoras
    1185 palabras | 5 páginas
  • Ensayo de la historia de la computadora
    734 palabras | 3 páginas
  • Ensayo Sobre Historia De Las Computadoras
    1133 palabras | 5 páginas
  • Ensayo el futuro de las computadoras
    1170 palabras | 5 páginas
  • Personajes de la Quinta Generación de Computadoras
    722 palabras | 3 páginas
  • Ensayo computadora cuantica
    1075 palabras | 5 páginas
  • Ensayo como hacer una tesis
    1223 palabras | 5 páginas
  • Ensayo Sobre Redes De Computadora
    1694 palabras | 7 páginas