Teoría de la computabilidad

La teoría de la computabilidad , también conocida como teoría de las funciones recursivas, es una rama de las matemáticas modernas que se encuentra en el cruce de la lógica matemática , la teoría de los algoritmos y la informática , que surgió como resultado del estudio de los conceptos de computabilidad y no computabilidad. -computabilidad. Inicialmente, la teoría se dedicó a funciones computables y no computables y la comparación de diferentes modelos de computación . Ahora el campo de estudio de la teoría de la computabilidad se ha expandido - aparecen nuevas definiciones del concepto de computabilidad y hay una fusión con la lógica matemática , donde en lugar de computabilidad y no computabilidad, estamos hablando de demostrabilidad y no demostrabilidad (deducibilidad y no computabilidad). -derivabilidad) de los enunciados en el marco de cualquier teoría.

La teoría de la computabilidad tiene su origen en el trabajo de Alan Turing ( 1936 ) "On Computable Numbers, With An Application to Entscheidungsproblem", en el que introdujo el concepto de computadora abstracta, que más tarde recibió su nombre, y demostró el teorema fundamental sobre la insolubilidad del problema de detenerlo . El famoso teorema de incompletitud de Gödel ( 1931 ) se demostró en términos de funciones recursivas primitivas , cuya clase Gödel extendió en 1934 a la clase de funciones recursivas generales . El formalismo desarrollado por Gödel resultó ser equivalente al de Turing (así como a muchos otros). Junto con la tesis de Church-Turing, este hecho demostró claramente el contenido de la nueva teoría, y ahora estas definiciones son generalmente aceptadas como un análogo formal de las funciones algorítmicamente computables.

La definición de funciones computables de Gödel era de naturaleza sintáctica, y sólo el establecimiento de la coincidencia de esta clase con la clase de funciones recursivas generales (junto con la formulación y "aceptación" de la tesis de Church) mostró el significado real del teorema de incompletitud.Ershov, Yuri Leonidovich

Véase también

• teorema de arroz
• detener el problema

• Kurt Godel
• alan turing
• Esteban Kleene
• Iglesia de Alonso
• Correo electrónico

Literatura

• Boolos J., Jeffrey R. Computabilidad y lógica. — M .: Mir, 1994. — 396 p.
• Ershov Yu.L. Teoría de la numeración. — M .: Nauka, 1977. — 416 p.
• Cutland N. Computabilidad. Introducción a la teoría de funciones recursivas.- M. : Mir, 1986. - 256 p.
• Kleene. Introducción a las metamatemáticas. - M. : Editorial de literatura extranjera, 1957. - 526 p.
• Maltsev I.A. Algoritmos y funciones recursivas. - M. : Nauka, 1965. - 392 p.
• Manin Yu.I. Computables y no computables. - M. : radio soviética, 1980. - 128 p.
• Minsky M. Cómputos y autómatas. - M. : Mir, 1971. - 366 p.
• Hodgers H. Teoría de funciones recursivas y computabilidad efectiva. - M. : Mir, 1972. - 624 p.
• Barweis J. Un libro de referencia sobre lógica matemática en cuatro partes. Parte III. Teoría de la recursividad.. - M. : Nauka, 1982. - 360 p.
• Uspensky V. A. Conferencias sobre funciones computables. - M. : Fizmatgiz, 1960. - 492 p.
• Uspensky V. A., Semenov L. A. Teoría de algoritmos: principales descubrimientos y aplicaciones. — M .: Nauka, 1987.
• Shenfield J. Grados de indecidibilidad. — M .: Nauka, 1977. — 192 p.

Enlaces