في الأعداد القابلة للحساب، مع تطبيق على مشكلة القرار (On Computable Numbers)

مقدمة

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.

الصلات

يستند إلى

• في القضايا الصورية غير القابلة للحسم في «مبادئ الرياضيات» والأنساق المرتبطة بها، 1 (Über formal unentscheidbare Sätze)1931 · كورت غودل

جرى تناوله في

• آلات الحوسبة والذكاء1950 · آلان تورنغ

مزيد من أعمال آلان تورنغ

• 1950آلات الحوسبة والذكاء