Ensayo: tesis de church-turing y la no computabilidad

873 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

  • Características de la tesis
    1837 palabras | 8 páginas
  • Ensayo De Las 11 Tesis Sobre Feuerbach
    633 palabras | 3 páginas
  • La maquina de turing
    2508 palabras | 11 páginas
  • Ensayo sobre la Tesis “Diseño de un manual para la organización profesional de un Diseñador Gráfico”
    1101 palabras | 5 páginas
  • Análisis comparativo entre ensayo, monografía y tesis
    1006 palabras | 4 páginas
  • La Aventura De Investigar: El Plan Y La Tesis
    8543 palabras | 35 páginas
  • Ensayo sobre las 95 tesis de Martín Lutero
    1112 palabras | 5 páginas
  • Tesis Sobre La Publicidad Y La Decision De Compra
    5961 palabras | 24 páginas
  • Variantes de la maquina de turing
    1452 palabras | 6 páginas
  • Maquina de Turing; ejercicios
    2108 palabras | 9 páginas