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