Premium
On Computable Numbers, with an Application to the Entscheidungsproblem. A Correction
Author(s) -
Turing A. M.
Publication year - 1938
Publication title -
proceedings of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.899
H-Index - 65
eISSN - 1460-244X
pISSN - 0024-6115
DOI - 10.1112/plms/s2-43.6.544
Subject(s) - turing , computer science , citation , turing machine , non deterministic turing machine , information retrieval , mathematics , universal turing machine , library science , algorithm , programming language , computation
In a paper entitled "On computable numbers, with an application to the Entscheidungsproblem"* the author gave a proof of the insolubility of the Entscheidungsproblem of the "engere Funktionenkalkul". This proof contained some formal errors f which will be corrected here: there are also some other statements in the same paper which should be modified, although they are not actually false as they stand. is provable " is false (even with the new expression for Inst {q a S b S d Lq c }): we are unable for example to deduce F (~ n+1)-> (—F(u, u")\ and therefore can never use the term
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom