On Computable Numbers, with an Application to the Entscheidungsproblem (O liczbach obliczalnych z zastosowaniem do problemu rozstrzygalności)

Wprowadzenie

Turing, a young fellow of King’s College, Cambridge, came to the problem through Max Newman’s lectures on the foundations of mathematics in 1935: Hilbert had asked whether there is a mechanical method for deciding of any formula of logic whether it is provable. The London Mathematical Society received the paper in May 1936, and it appeared in its Proceedings in 1936–37. Turing analyses what a person does when calculating by rule and reduces it to a machine with finitely many states that reads, writes and moves along an unbounded tape; “computable numbers” are the real numbers whose decimals such a machine can write out. He shows that a single universal machine can imitate any other if given its description, and that no machine can decide of every machine whether it will ever print a given symbol – from which the negative answer to Hilbert’s question follows. Alonzo Church had published the same answer shortly before, using his lambda calculus; in an appendix Turing proved the two notions of computability equivalent, and in the autumn of 1936 he went to Princeton, where he took his doctorate under Church in 1938.

Powiązania

Nawiązuje do

• O formalnie nierozstrzygalnych zdaniach Principia Mathematica i pokrewnych systemów I1931 · Kurt Gödel

Podjęte w

• Maszyny liczące a inteligencja1950 · Alan Turing

Więcej dzieł: Alan Turing

• 1950Maszyny liczące a inteligencja