computable which is equivalent to my computability effective calculability m-configurations tape squares symbol in the machine . The symbol on the scanned square may be called the . The directly aware seen An unsolvable problem of elementary number theory A note on the Entscheidungsproblem machine tape scanned automatic machine possible circular b c £ 0 1 R . Similarly for . means and stands for o q p f b o x 1 aoO keep the place skeleton tables variables ' first a ?/i-configuration function m-function -> a D A D C C L R N 2 3 L 4 by and ft» 2*3®o^2- D and'' C 0 DC 1 DCC DA A DCCC q DAAA rough work :: JD L i2 JV u v w z y } Print 0 Print 1 there must be something wrong circle-free s 5 s there is a general process for determining... n is satisfactory computable distance state of mind simple operations observed immediate recognisability ... hence (applying Theorem 157767733443477) we have ... immediately recognisable m-configuration The rc-th figure of a is 1 x is a non-negative integer y = x-\-l 2( defines a the functional calculus + i1 2 A B 21 defines a state of mind state formula uniformly computably convergent r(x) = y (f>(x y) = z F F q{ 8i Sk Lqt where 230 A. M. TUKING Nov. 12 ON COMPUTABLE NUMBERS WITH AN APPLICATION TO THE ENTSCHEIDUNGSPROBLEM By TURING. Received 28 May 1936.—Read 12 November 1936. The numbers may be described briefly as the real whose expressions a decimal are calculable by finite means. Although subject of this paper is ostensibly numbers. it almost equally easy to define and investigate functions an integral variable or variable predicates so forth. fundamental problems involved are however same in each case I have chosen for explicit treatment involving least cumbrous technique. hope shortly give account relations numbers functions forth one another. This will include development theory expressed terms According my definition number if its can written down machine. In §§ 9 10 some arguments with intention showing that all which could naturally regarded computable. particular show certain large classes They include instance parts algebraic zeros Bessel IT e etc. do not definable example given not class great many Avays similar nevertheless enumerable. § 81 examine would seem prove contrary. correct application these arguments conclusions reached superficially those Gbdelf. These results f Godel " Uber formal unentscheidbare Satze der Principia Mathematica und ver- •vvandter Systeme I" . Monatsheftc Math. Phys. 38 (1931) 173-198. NUMBERS. 231 valuable applications. shown (§11) Hilbertian Entscheidungsproblem no solution. recent Alonzo Church has introduced idea "effective calculabilitycomputability" but very differently defined. also reaches about EntscheidungsproblemJ. proof equivalence between outlined appendix present paper. 1. Computing machines. We said decimals requires rather more definition. No attempt made justify definitions until we reach 9. For shall only say justification lies fact human memory necessarily limited. compare man process computing i capable conditions q1: q2. .... qI called supplied (the analogue paper) running through it divided into sections (called ) bearing At any moment there just square r-th <2>(r) call square "scanned symbolscanned symbol" is speak However altering m-configuration effectively remember symbols (scanned) previously. behaviour at determined ra-configuration qn (r). pair qn © (r) '' configuration'': thus configuration determines configurations blank (i.e. bears symbol) writes new on square: other erases symbol. change being scanned shifting place right left. addition operations changed. Some Church American J. Math. 58 (1936) 345-363. X Symbolic Logic 40-41. 232 TURING form sequence figures computed. others rough notes "assist ". It liable erasure. contention used computation number. defence easier when machines familiar reader. next section therefore proceed assume understood what meant 2. Definitions. Automatic If stage motion (in sense 1) completely configuration (or a-machine). .For purposes might use (choice c-manhines) onty partially (hence word §1). When such ambiguous configurations cannot go arbitrary choice been external operator. case were using deal axiomatic systems. automatic machines often omit prefix a-. a-machine prints two kinds symbols first kind figures) consists entirely second kind) then set motion starting from initial ra-configuration subsequence sjinbols printed computed expression binary obtained prefacing point machine complete tape describe stage. changes successive moves 233 Circular never than kind circular. Otherwise circle-free. move goes moving possibly printing print kind. significance term explained §8. Computable sequences differs integer avoid confusion speaking 3. Examples I. constructed compute 010101.... four m-configurations "c:> following table means "the scans immediately was scanning previouslyLEthe erasedP prints". (and succeeding tables kind) mean columns third column carried out successively over last column. left blank fourth applies starts tape. -config. Configuration m-config. None Behaviour final PO PI t 234 NOV. (contrary description allow letters L appear once simplify considerably. PO R PI 6 II. As slightly difficult construct 001011011101111011111 five ra-configurations viz. three follow alternate squares. On intermediate anything serve us erased finished them. arrange blanks. Pa • { fAny (0 rt J q i g ^ 1I Po PO. i? Px E RR p To illustrate working below few configurations. writing 235 separated colons. : 99 Oroo O 0:99 :99 9 1:99 P :oa H-0: :9 ... (C) space the* space. less follow make later theoretical purposes. convention useful: always it. JF'-squares ^/-squares. oi •. ^-squares F-squares continuous sequence. There blanks end reached. need jE'-square .F-squarcs apparent ^/-squares satisfied having sufficiently rich variety ^-squares. /3 F-square S ^-square S marked a. marking jS S) 4. Abbreviated tables. types nearly and. these connections. processes copying comparing sequences erasing form Where concerned abbreviate considerably skeleton capital German small Greek letters. nature replacing letter throughout ^^-configuration 236 symbol obtain m-configuration. nothing abbreviations: they essential. So long reader understands how tables exact connection. Let consider example: f(eS5a) fi(693a) Symbol Final f^G 95 a) f(<5S3a) f2(G From f(@ 93 finds farthest ?w-configuration becomes (L 93. I 93 replace (say) r x should (q x). admissible substitution »i-function enumerated explicitly: p(c x) indeed must m-functions all. did insist eaumeration simply stated had (enumerated) obtainable m-function.-J .should usually get infinity m-configurations e.g. substituting p(£). Then q p(q) pfp(q)V p(p(p(q))) ... asm-configurations. Our interpretation rule this. names ^-configurations mostly m-functions. All want repeated 237 Further examples. (In explanations signify ra-configuration. ") e((523a) (e^S S3 a) c(S 23 „ c^G # G c(S3 c(c(S3 -»53. seems somewhat interpret most. suppose list appears c('b x) (=q saj'). c(6 a) e(c(b h c(q 6 a). Or greater detail: (ci(q a.1 ) t) Cj.(q I) re) £• q. cJL(q q' (with substitutions) eventually appeared. j8) (pc^G j8) €Q) pc (g /3) Any i?3JR pe^S.jS) rint ue ( \ sj^mbols None P/S I(S) f'((5: 2J does r/gx j f(6 before -^ <3. f(6»o) f(t(6)a3a) f"(S»o) f(t(S)S8a) c(SS3o) f'(c-i(S) 55 c(<£ a). ( pe(€ JS) £. 238 line stands totality lines fi occur concerned. cc(£S3a) c(e(GS3a)83a) ce(23 copies order cc(23a) ce(ce(83a)23a) a ->SS. vc(G93aj8) f(re1(g3$B3ai8)^5a) rc(£ a 0). replaces re^^a.fl EPp (8 and->g 35 re(S P) re («(» «<»' a> #• Th e machin places S ->S5. cr(Ci23a) c(tt(G9$aa) S3a) Cr(83 011137" «(«(5Sa)rc(SSaa)a) erased. cv(5S taken up •r (C. 21 e. 5) (cpi S( )S) f(3t g cp(C 2li8) 7 (cp2(e2T y) cp.((S. 2( y) noty SI. 8 compared. neither nor ft —> (I\ both alike (5. 21. cpc(6 SI G jS) cp (c (e((5 yS) ^) cpe(S cp(§ £ similarity /? cpe^ Q cpe (cpe(Sl )3). cpe(2I j8). compared /?. Q similar. 239 JAny ce2(95 ce3(S5a @. j8y) Any 3)> pc2(S jS). j8 end. ce(ce(255j8) ce3(S5aj8y). ce (ce2(S50 r jS finally y /? y. e1((5) e(^) marks ^> symbols. 5. Enumeration sequences. computes Thus 001011011101111... p. 234 and fact table. useful put standard form. let table example 233. That say entry forms E :ER:EL:Pa: R: L:R:L: introducing m-configurations. Now w-configurations calling them qx qR §1. qv #_..... Sm 240 TUBING = 80 Slt S2. hnes now Operations Lines ft s Si s. PSkL PSkiR PSk PS0 PS way reduce (Nj (N2) (i\y. (N^ q( SjSb qm (N2) qiSjSkRqm (N3) #•# SkNqm. write formed separate semi-colons. q{ followed times $- times. (S.D). '5N6*3> £< 7" shall arabic numeral. represented numeral (D.N) D.N determine S.D structure 241 uniquely. n corresponds number while correspond find rename becomes: q-L *b1} K q2 SQ P8O q3 PS2) #4 PSo>R Other adding irrelevant qx Sx PSVR qxOQOJRq%j q%^o^o-ft' ft^o^oRQ\J• DADDCRDAA DAADDRDAAA I^^DDCCtfi)^ \DAAAADDRDA 31332531173113353111731113322531111731111335317 3133253117311335311173111332253111173111133531731323253117 satisfactory 8 general determining whether not. 6. universal invent single M beginning .At 8KR. VOL. 42. NO. 2144. B 242 'It explain outline devoted giving U. it' .F-squares 235 description (C) line. better transform (as §5) appropriate letters'' agree §5 that replaced substitutions after together (C). Difficulties arise first. II DA .DCCCDCCCDAADCDDC.DCCCDCCCDAAADCDDC:... (CJ (This ^-squares.) see constructed it'. manner operation depend rules {i.e. S.D) il somewhere within itself {i.e. il/) step referring rules. regard exchanged something akin One thing lacking figures. old. (C^) DDA:O:O:DCCCDCCCDAADCDDC:DCCC... (C2) altogether obvious leave enough room necessary case. colons (Cj) descriptions figures 5 numerical e^onf) c(anf) ei(anf) anf 243 •description 7. Detailed •m-configurations occurring together unabbreviated E.g. e(anf) wi-fimction. Its (see 239) e^anf) Consequently e1(anf) \l ready start work .F-square again i£-square this only comes double colon (a .F-square). instructions Each instruction consecutive (i) describes relevant (ii) (iii) another (iv) describing move left right (v) U ctD0" • ((RN". 244 Subsidiary (Not con(£ con(@ con^CE con2(§ con(@. Starting J^-square seA con^S quenc describA RPaR con^a ing closest ->@. Not R.R con2(£a) con(S ). C. unmarked. hx RRP:RRPDRRPA ->anf. font Pz: LL g(anf1} :) anf. COn (font comp - !om con (limp font. semi-colon z. x. Hnr> cpe(c(fom iim fmp. compares Sim alike. ->• Taking view found. recognised afterwards -Mim. 245 •mt m?3 m?4 mh RPu LPy Py R (stm2 e(mB Pa j^ Z' P: ? •R 22 mf2 Pv m!3 mL mf6 inSt 0 xnit im. instructions. part instructions refers u mconfiguration mi. sections. configiiraration directly preceding remainder parts w. whole. $f. u) Sf. (marked examined. found involve 0: 1: 246 in«t fl(t(in«1)tt) «**• nex down. in^t1(a) carrying instrucL) ce5(o».t> y w) tions u> v> w> x> V -^anf. i?) ce5(o» v \nitx{N) ec5(ot> co 8. Application diagonal process. thought enumerable enumerable*. might limit clearly true defined rule. Or apply "If enumerable a/( n-th sequence l(ra) ?n-th figure au. \—n(n) n-th. figure. Since computable exists l—cf)ll(n) n. Putting K 2(f>K(K) i.e. even. impossible. enumerable". fallacy argument assumption enumerate means problem enumerating equivalent finding doing steps. applying correctly simplest most direct exists proof although perfectly sound disadvantage feeling disadvantage gives insight depends constructing /3 fi' n{n). * Cf. Hobson Theory (2nd ed. 1921) 87 88. 247 process which l test mark combining <& :l I- j8'. require uses jE'-squares beyond .F-squares verdict done l0- Ji N— sections among things integers 1 2... tested -. R(N— D.N's N-th (& tests N. satisfactory i.e. R(N) l-\-R(N—l) R{N) $£N calculated. R(N)-th sequence/3' Ji. (iV-(-l)-th motion. construction .11- For our decision satisfactor}' JV-th finished. il(JV) circle-free J?(iV)-th calculated /3' iV-th Hence What K-th. JI- since JI hand were bound R(K—1) + R(K) R(K)-th ill. — calculating R(K)-th. amount "calculate H R(K)-th". R{K)-th I.e. 'i-l circular contrary paragraph verdicts impossible conclude '0-. 248 further iviih AV vjhether AV ever say). U< infinitely often. Jlx A\ except position where stands A\x 0. U2 s\aribols on. Thus Uwere ABAQlAABOQIOAB... A\± ABA01AAB0010AB... .112 ABAoiAAB~00l0AB.... Xow H .U successively .11 .lll5 U2 (there machine). combine V' I' Xj. ( > -U it.: o: iy 11 0 II2 tested.. Ux 0) KOAV .< ('. X .H often Xj sometimes .11 Similarly U- combination whether. "there usage justified definition "general process: ' concerning Avhether property G(n) e.g. G{n) "n Godel representation provable formula" (n) false. Otf 249 extent yet Al be fundamentally appeals intuition reason unsatisfactory mathematically. question issue number?" kinds. (a) appeal intuition. (6) intuitive appeal). (c) Giving examples Once granted c: computable"". several propositions character follow. follows formula Hilbert function calculus provable determination bo Type (a). elaboration ideas normally "We like child's arithmetic book. elementary two-dimensional sometimes used. But avoidable think agreed essential computation. one-dimensional paper finite. differing arbitrarily effect restriction serious. Arabic literally < points occupied printer's ink. sets restricted measurable cost transforming moving unit area ink unity infinite supply With topology conditionally compact 250 17 999999999999999 treated European language words (Chinese attempts symbols). differences view compound too lengthy glance. accordance experience. tell glance 9999999999999999 same. computer he observing his moment. observe wishes more observations. states mind reasons restrict admitted mind close confused. Again seriously affects computation complicated avoided imagine performed split divided. Every physical system consisting know state (possibly special order) computer. simple altered. situation altered may therefore without loss generality changed Besides distribution recognisable reasonable previously exceed fixed amount. square. connection recognisable. imme- 251 diately them upset adjoining If. hand recognition illustrated. mathematical papers equations theorems numbered. Normally (say) 1000. recognise theorem long Theorem 157767733443477 then sure figure ticking off pencil their counted twice. spite still squares type capable. developed III below. include: Changes mind. following: (A) (B) actually determined suggested 250 out. corresponding distant 252 12. done differ essentially 2 (6). notation functional modified systematic symbols3 3C formulae calculus§. denote Ga(x) proposition that1 —Ga(x) "The z-th Suppose properties prepositional N(x) meaning F(x join conjunctively formula % defines 21 Peano axioms viz. N(x)-»(3y)F(x y)) &(F(X P. —21 n (AJ (BJ provable. %&Ftn ^Ga(uW) (AB)«T F™ F{u u') & F(u' u") F^-v u™). calculus. natural (§ 2) required choice3 choices possibilities ilt i2 •?•„ (ix 1) hence 2~^-\-i22"---\-...-\-in proof. carries 3 author negation sign *\ primes denoted '''-1 253 sequence: 'JCa fairly modification JC divide Ka After (n— l)-th :: wholly colon. (An) (Bn). JC whenever found (An) printed (BJ different both continued abandoned. Sooner (B?1) reached hypotheses known JC. 3CO circle-free axioms remembered attached phrase ordinary sense) according satisfactory. immediate consequence (so far present) assigned calculated uniform method necessaiy III. corollary suppose tape considering definite counterpart break work away forget come back note (written form) explaining continued. works desultory sitting. enable him carry note. progress 254 (sequence symbols) (which elsewhere) made relation expressible words axiom 2( expresses governing computer so formulae 10. begin ways defining variable. possibly follows. infinitely! often integer £(y n) (?i-\- if .(n) n). An H(x Then contradiction-free 21^ 2^-* P N m=£(n) N' function. yn ./U {n) | *Al 255 unless either cases runs numbersf. value %. / f(an) a^n) Similar variables computable-valued enunciate computability (iii). recursively I.e. 0(ra rj(n) (m {n (j>(n) fi-th (n) Dedekind's hold *' real'' computable''. holds G(a) propositional (3a)(3jB){G(a)&(-G(j8))} Q(a) truth G(a) run 256 12r computables belongs. Owing theorem bounded increasing limit. ± -5 5 io 2» ••• enables (vi) <£(a) (/?) (f>(a) function unique satisfying (y) convergence. fin converges computably valued N(e) m N(e) \pn—j8m| (vii) power series coefficients convergent interior interval (viii) And (ix) uniformly (x) sum TT— 4(1—i-|--i—...) deduce TT e= l+n-j-+»-j+... OlST 257 Proof (ii). K{x z) 21^ (x y). take 31 (F{x y)-*Q{x G{x G(y z)->G(x z)) (FW-*H{U VP>)) (J(v #(v Z(w x} z)->H(iv £f(w ^(2 <)v (?(< consistency %n. Such methods Bernays Grundlagen Mathematik (Berlin 1934) 209 et seq. clear meaning. M Also ST Also M'^M if'^ m^r)(u) FW^G^W) u^) G(u^m\ 8EB. 2145. 258 FW)-^ {G(u^n ^ w(m)) FW"> (-H{u^ u™)). satisfied. rj Tl P-squares b depending n(m) m-th yv n{n) Tl byl. made. 95 te(23 k) re(93 t> add lines: pe(ul5 Uj. Pk P0 P0 u2 re(u3 u3 k h) u3 pe(u2 F) PE Ph (H/ jS. c aa Pi 259 11. Entscheidungsproblem. important confine myself proving particular theorem. formulation refer Ackermann's Grundziige Theoretischen Logik 1931) chapter propose perhaps remarked quite well-known Godelf. odel formalism Mathematica) '21 •of K) formalism. tells or same adjoined cextra consistent. proved solution consecutively formulae. —21. consistent (Hilbert Ackermann 65) absence proofs lengthy. underlying straightforward. Corresponding Un (it) (.11) interpretations Rst( V) interpreted "in (of J/l) S". Loc. cit. S2 260 I(x scanned". KQm(x) qm. sty successor Inst {qt Sj 8k 37} abbreviation (x x' y') (BSj(x k K8i(x) x') F(y' I{x'iy')kBSk{x'y)kKqi{x') (z) \_F{y' z)v(RSj(x Rak(x' {q{ 8 Sk qt} 8j q{ abbreviations similarly expressions. ROT substituted L). $3- logical sum. Des(.U). Un(.U) {3u)N{u) & (x)(N{x)->{3x')F(x X')) &. (y z)(F(y z)->N(y) N(z)) (y) R>%(% I(u Kqi{u) Des(..U)l ->(35) (30 N(s) N(t) RSl(s t)). K{u)&... &Des(.U) abbreviated A(M). substitute meanings 259-60 S-^ U Un(U) (b) (• U) 8X trivial. 261 LEMMA / S± Un(.At) (it). &r(no)> *^r(ni)5 •••> $i blanks i(n)-th q^n). RSrluJvF> RSr{HMn CCn. before F{u' F{u^\ w(r)) F A{-W) F™^- CCn (abbreviated CFn) CFn actual expected. CF0 certainly CC0 RSo{u KQl(u). A(o\i)->CC0 CFn^-CFn+1 consider (n-j-l)-th remains stationary. applies cases. rni(n)}=a r(n-\-l i(n-\-l)} k(i(n)j =b k(i(n-\-l)) =d Des {qa 8b Sd q^ terms A(.AV) Fin +n^1nat{qa8b8dLqc} Inst{qa Sb 8dLqc} +w^(CCn It) F(n +»-> (CCn -» C(L . 262 (AIM) F™^CCn) -+ (.4(it) F +V^CCn+1) CFm-»CF.n+V lemma 8± somewhere M CGN RS(u^N \u^) CCN^RSl{u{N\ u(K)) A(.M)&FW->CCN (3u)A(M)-+(3u)(3uf )... N' max (N K). (3u) (. U.) (3^7 )) (3uW) RS (3u)A(M)->(3s)(3t)RSl(st) Un(-U) completes Lemma S1 variables proposition. tabulated pp. 259-260 Un(^U) .M". solved. (mechanical) Un(.tl) Lemmas implies .41 impossible solutions Entscheidung