%PDF-1.4 5 0 obj << /S /GoTo /D (chapter*.1) >> endobj 8 0 obj (Thank You) endobj 9 0 obj << /S /GoTo /D (chapter.1) >> endobj 12 0 obj (Introduction) endobj 13 0 obj << /S /GoTo /D (section.1.1) >> endobj 16 0 obj (Undecidability everywhere?) endobj 17 0 obj << /S /GoTo /D (section.1.2) >> endobj 20 0 obj (And now for something completely different?) endobj 21 0 obj << /S /GoTo /D (subsection.1.2.1) >> endobj 24 0 obj (Computability and ``Computability'') endobj 25 0 obj << /S /GoTo /D (subsection.1.2.2) >> endobj 28 0 obj (Diagonalization and Reducibility) endobj 29 0 obj << /S /GoTo /D (section.1.3) >> endobj 32 0 obj (Questioning unsolvability.) endobj 33 0 obj << /S /GoTo /D (section.1.4) >> endobj 36 0 obj (General Outline and research Questions) endobj 37 0 obj << /S /GoTo /D (subsection.1.4.1) >> endobj 40 0 obj (Short Description of the chapters.) endobj 41 0 obj << /S /GoTo /D (section.1.5) >> endobj 44 0 obj (A small note to the reader.) endobj 45 0 obj << /S /GoTo /D (part.1) >> endobj 48 0 obj (I Re-Tracing) endobj 49 0 obj << /S /GoTo /D (chapter.2) >> endobj 52 0 obj (The Beginnings) endobj 53 0 obj << /S /GoTo /D (section.2.1) >> endobj 56 0 obj (General Background) endobj 57 0 obj << /S /GoTo /D (section.2.2) >> endobj 60 0 obj (From solvability to unsolvability) endobj 61 0 obj << /S /GoTo /D (subsection.2.2.1) >> endobj 64 0 obj (Introduction) endobj 65 0 obj << /S /GoTo /D (subsection.2.2.2) >> endobj 68 0 obj (Focus on Form) endobj 69 0 obj << /S /GoTo /D (subsection.2.2.3) >> endobj 72 0 obj (The Problem of ``Tag''.) endobj 73 0 obj << /S /GoTo /D (subsection.2.2.4) >> endobj 76 0 obj (Further reductions: From tag systems to Post's thesis) endobj 77 0 obj << /S /GoTo /D (subsection.2.2.5) >> endobj 80 0 obj (Conclusion) endobj 81 0 obj << /S /GoTo /D (section.2.3) >> endobj 84 0 obj (``To deny what seems intuitively natural'') endobj 85 0 obj << /S /GoTo /D (subsection.2.3.1) >> endobj 88 0 obj (Introduction) endobj 89 0 obj << /S /GoTo /D (subsection.2.3.2) >> endobj 92 0 obj (Towards variant systems of logic.) endobj 93 0 obj << /S /GoTo /D (subsection.2.3.3) >> endobj 96 0 obj (An Inconsistent Set of Postulates) endobj 97 0 obj << /S /GoTo /D (subsection.2.3.4) >> endobj 100 0 obj ( - The Ultimate Operator) endobj 101 0 obj << /S /GoTo /D (section.2.4) >> endobj 104 0 obj (From typewriters to universal computing machines) endobj 105 0 obj << /S /GoTo /D (subsection.2.4.1) >> endobj 108 0 obj (Introduction) endobj 109 0 obj << /S /GoTo /D (subsection.2.4.2) >> endobj 112 0 obj (Typewriters and ``Little wonders'') endobj 113 0 obj << /S /GoTo /D (subsection.2.4.3) >> endobj 116 0 obj (The central limit theorem) endobj 117 0 obj << /S /GoTo /D (subsection.2.4.4) >> endobj 120 0 obj (Newmann's course on the foundations of mathematics) endobj 121 0 obj << /S /GoTo /D (section.2.5) >> endobj 124 0 obj (Conclusion) endobj 125 0 obj << /S /GoTo /D (chapter.3) >> endobj 128 0 obj (1936) endobj 129 0 obj << /S /GoTo /D (section.3.1) >> endobj 132 0 obj (Different questions, different answers.) endobj 133 0 obj << /S /GoTo /D (subsection.3.1.1) >> endobj 136 0 obj (``An Unsolvable Problem of Elementary Number Theory'') endobj 137 0 obj << /S /GoTo /D (subsection.3.1.2) >> endobj 140 0 obj (``On computable numbers, with an application to the Entscheidungsproblem'') endobj 141 0 obj << /S /GoTo /D (subsection.3.1.3) >> endobj 144 0 obj (``Finite Combinatory processes. formulation 1'') endobj 145 0 obj << /S /GoTo /D (section.3.2) >> endobj 148 0 obj (On the status of the identification) endobj 149 0 obj << /S /GoTo /D (subsection.3.2.1) >> endobj 152 0 obj (Church's reviews of Post's and Turing's paper) endobj 153 0 obj << /S /GoTo /D (subsection.3.2.2) >> endobj 156 0 obj (On the adequacy of Turing's identification: From definition to theorem.) endobj 157 0 obj << /S /GoTo /D (subsection.3.2.3) >> endobj 160 0 obj (The identification as \(hypo\)thesis or law.) endobj 161 0 obj << /S /GoTo /D (subsection.3.2.4) >> endobj 164 0 obj (Some further developments.) endobj 165 0 obj << /S /GoTo /D (section.3.3) >> endobj 168 0 obj (Strategies against intuition.) endobj 169 0 obj << /S /GoTo /D (subsection.3.3.1) >> endobj 172 0 obj (The thesis as a definition. On the significance of using the right formalism for the development of the theory.) endobj 173 0 obj << /S /GoTo /D (subsection.3.3.2) >> endobj 176 0 obj (Different intuitions, different formalisms) endobj 177 0 obj << /S /GoTo /D (subsection.3.3.3) >> endobj 180 0 obj (``Testing in practice'': Studying formalisms instead of intuitions) endobj 181 0 obj << /S /GoTo /D (subsection.3.3.4) >> endobj 184 0 obj (Can we trust our intuition?) endobj 185 0 obj << /S /GoTo /D (chapter.4) >> endobj 188 0 obj (The computer.) endobj 189 0 obj << /S /GoTo /D (section.4.1) >> endobj 192 0 obj (The first computers) endobj 193 0 obj << /S /GoTo /D (subsection.4.1.1) >> endobj 196 0 obj (The ENIAC and the EDVAC) endobj 197 0 obj << /S /GoTo /D (subsection.4.1.2) >> endobj 200 0 obj (Alan Turing's work on computers and programming) endobj 201 0 obj << /S /GoTo /D (subsection.4.1.3) >> endobj 204 0 obj (Zuse's Z1, Z2, Z3, Z4 and Plankalk\374l) endobj 205 0 obj << /S /GoTo /D (subsection.4.1.4) >> endobj 208 0 obj (Conclusion.) endobj 209 0 obj << /S /GoTo /D (section.4.2) >> endobj 212 0 obj (Exploring the ``universe of discourse'') endobj 213 0 obj << /S /GoTo /D (subsection.4.2.1) >> endobj 216 0 obj (von Neumann and theoretical physics.) endobj 217 0 obj << /S /GoTo /D (subsection.4.2.2) >> endobj 220 0 obj (Lehmer's computational work on number theory.) endobj 221 0 obj << /S /GoTo /D (subsection.4.2.3) >> endobj 224 0 obj (Conclusion) endobj 225 0 obj << /S /GoTo /D (section.4.3) >> endobj 228 0 obj (Going beyond or not beyond the Turing limit?) endobj 229 0 obj << /S /GoTo /D (subsection.4.3.1) >> endobj 232 0 obj (On the practical feasibility of the computable: Computational Complexity Theory.) endobj 233 0 obj << /S /GoTo /D (subsection.4.3.2) >> endobj 236 0 obj (The land of Tor'bled-nam. To solve the unsolvable.) endobj 237 0 obj << /S /GoTo /D (subsection.4.3.3) >> endobj 240 0 obj (Conclusion) endobj 241 0 obj << /S /GoTo /D (section.4.4) >> endobj 244 0 obj (Conclusion.) endobj 245 0 obj << /S /GoTo /D (part.2) >> endobj 248 0 obj (II Tagging) endobj 249 0 obj << /S /GoTo /D (chapter.5) >> endobj 252 0 obj (Why Tag systems?) endobj 253 0 obj << /S /GoTo /D (chapter.6) >> endobj 256 0 obj (Preliminaries) endobj 257 0 obj << /S /GoTo /D (section.6.1) >> endobj 260 0 obj (Discussion of published results on tag systems.) endobj 261 0 obj << /S /GoTo /D (subsection.6.1.1) >> endobj 264 0 obj (General Theoretical results) endobj 265 0 obj << /S /GoTo /D (subsection.6.1.2) >> endobj 268 0 obj (``Tag -- you are it'': Some concrete research on tag systems.) endobj 269 0 obj << /S /GoTo /D (subsection.6.1.3) >> endobj 272 0 obj (Conclusion) endobj 273 0 obj << /S /GoTo /D (section.6.2) >> endobj 276 0 obj (General classes of behaviour in tag systems) endobj 277 0 obj << /S /GoTo /D (subsection.6.2.1) >> endobj 280 0 obj (Description of classes of behaviour) endobj 281 0 obj << /S /GoTo /D (subsection.6.2.2) >> endobj 284 0 obj (``Unpredictable iterations.'') endobj 285 0 obj << /S /GoTo /D (subsection.6.2.3) >> endobj 288 0 obj (Classes of behaviour and the two forms of the problem of ``tag''.) endobj 289 0 obj << /S /GoTo /D (subsection.6.2.4) >> endobj 292 0 obj (Conclusion) endobj 293 0 obj << /S /GoTo /D (section.6.3) >> endobj 296 0 obj (Shifting through tags) endobj 297 0 obj << /S /GoTo /D (subsection.6.3.1) >> endobj 300 0 obj (An example of a solvable tag system.) endobj 301 0 obj << /S /GoTo /D (subsection.6.3.2) >> endobj 304 0 obj (Generalization of the example.) endobj 305 0 obj << /S /GoTo /D (chapter.7) >> endobj 308 0 obj (Constraints for intractable behaviour) endobj 309 0 obj << /S /GoTo /D (section.7.1) >> endobj 312 0 obj (Introduction) endobj 313 0 obj << /S /GoTo /D (section.7.2) >> endobj 316 0 obj (Notational Conventions) endobj 317 0 obj << /S /GoTo /D (section.7.3) >> endobj 320 0 obj (Description of the Constraints) endobj 321 0 obj << /S /GoTo /D (subsection.7.3.1) >> endobj 324 0 obj (Constraint 1: Post's condition) endobj 325 0 obj << /S /GoTo /D (subsection.7.3.2) >> endobj 328 0 obj (Constraint 2: The Wang condition) endobj 329 0 obj << /S /GoTo /D (subsection.7.3.3) >> endobj 332 0 obj (Constraint 3. Proportions between \043ai.) endobj 333 0 obj << /S /GoTo /D (subsection.7.3.4) >> endobj 336 0 obj (Constraint 4. The table method.) endobj 337 0 obj << /S /GoTo /D (subsection.7.3.5) >> endobj 340 0 obj (Constraint 5. On the number of iterations.) endobj 341 0 obj << /S /GoTo /D (section.7.4) >> endobj 344 0 obj (Generating intractable tag systems) endobj 345 0 obj << /S /GoTo /D (subsection.7.4.1) >> endobj 348 0 obj (Algorithm 1: Two-symbolic tag systems, v-lw0 = lw1 - v) endobj 349 0 obj << /S /GoTo /D (subsection.7.4.2) >> endobj 352 0 obj (Algorithm 2: Two-symbolic tag systems, v-lw0 =lw1 - v) endobj 353 0 obj << /S /GoTo /D (chapter.8) >> endobj 356 0 obj (Playing with Tag Systems) endobj 357 0 obj << /S /GoTo /D (section.8.1) >> endobj 360 0 obj (Purpose of the chapter) endobj 361 0 obj << /S /GoTo /D (section.8.2) >> endobj 364 0 obj (Some further restrictions) endobj 365 0 obj << /S /GoTo /D (subsection.8.2.1) >> endobj 368 0 obj (On the programming language used.) endobj 369 0 obj << /S /GoTo /D (subsection.8.2.2) >> endobj 372 0 obj (Size of Sample space vs. computation time) endobj 373 0 obj << /S /GoTo /D (subsection.8.2.3) >> endobj 376 0 obj (Focus on 2-symbolic tag systems) endobj 377 0 obj << /S /GoTo /D (section.8.3) >> endobj 380 0 obj (Experiment 1) endobj 381 0 obj << /S /GoTo /D (subsection.8.3.1) >> endobj 384 0 obj (Set-up of experiment 1) endobj 385 0 obj << /S /GoTo /D (subsection.8.3.2) >> endobj 388 0 obj (Discussion of the results) endobj 389 0 obj << /S /GoTo /D (section.8.4) >> endobj 392 0 obj (Experiment 2) endobj 393 0 obj << /S /GoTo /D (subsection.8.4.1) >> endobj 396 0 obj (Set-up of experiment 2) endobj 397 0 obj << /S /GoTo /D (subsection.8.4.2) >> endobj 400 0 obj (Discussion of the results) endobj 401 0 obj << /S /GoTo /D (section.8.5) >> endobj 404 0 obj (Experiments 3--6: Summary of the results.) endobj 405 0 obj << /S /GoTo /D (subsection.8.5.1) >> endobj 408 0 obj (Experiment 3) endobj 409 0 obj << /S /GoTo /D (subsection.8.5.2) >> endobj 412 0 obj (Experiment 4) endobj 413 0 obj << /S /GoTo /D (subsection.8.5.3) >> endobj 416 0 obj (Experiment 5) endobj 417 0 obj << /S /GoTo /D (subsection.8.5.4) >> endobj 420 0 obj (Experiment 6) endobj 421 0 obj << /S /GoTo /D (section.8.6) >> endobj 424 0 obj (Conclusion) endobj 425 0 obj << /S /GoTo /D (chapter.9) >> endobj 428 0 obj (Universality and Unsolvability in Tag Systems) endobj 429 0 obj << /S /GoTo /D (section.9.1) >> endobj 432 0 obj (Why are \(small\) universal machines interesting?) endobj 433 0 obj << /S /GoTo /D (subsection.9.1.1) >> endobj 436 0 obj (Size and definition of universal machines.) endobj 437 0 obj << /S /GoTo /D (subsection.9.1.2) >> endobj 440 0 obj (Small universal machines: an overview.) endobj 441 0 obj << /S /GoTo /D (section.9.2) >> endobj 444 0 obj (Why are \(small\) universal systems not interesting?) endobj 445 0 obj << /S /GoTo /D (subsection.9.2.1) >> endobj 448 0 obj (Minsky's 4-symbol, 7-state machine.) endobj 449 0 obj << /S /GoTo /D (subsection.9.2.2) >> endobj 452 0 obj (Generating a universal tag system.) endobj 453 0 obj << /S /GoTo /D (subsection.9.2.3) >> endobj 456 0 obj (Conclusion) endobj 457 0 obj << /S /GoTo /D (section.9.3) >> endobj 460 0 obj (Studying the ``universe of discourse'') endobj 461 0 obj << /S /GoTo /D (subsection.9.3.1) >> endobj 464 0 obj (The Busy Beaver Game) endobj 465 0 obj << /S /GoTo /D (subsection.9.3.2) >> endobj 468 0 obj (Busy Beavers and Collatz-like Problems) endobj 469 0 obj << /S /GoTo /D (subsection.9.3.3) >> endobj 472 0 obj (On the ``universality'' of cellular automaton rule 110.) endobj 473 0 obj << /S /GoTo /D (subsection.9.3.4) >> endobj 476 0 obj (Conclusion) endobj 477 0 obj << /S /GoTo /D (section.9.4) >> endobj 480 0 obj (Solvability and Unsolvability in Tag systems) endobj 481 0 obj << /S /GoTo /D (subsection.9.4.1) >> endobj 484 0 obj (Tag systems and Collatz-like problems) endobj 485 0 obj << /S /GoTo /D (subsection.9.4.2) >> endobj 488 0 obj (Solvability of the class = v = 2.) endobj 489 0 obj << /S /GoTo /D (subsection.9.4.3) >> endobj 492 0 obj (Universality in tag systems.) endobj 493 0 obj << /S /GoTo /D (subsection.9.4.4) >> endobj 496 0 obj (Discussion on the limits of solvability and unsolvability in tag systems) endobj 497 0 obj << /S /GoTo /D (section.9.5) >> endobj 500 0 obj (Conclusion.) endobj 501 0 obj << /S /GoTo /D (chapter.10) >> endobj 504 0 obj (Conclusion. Tracing Unsolvability) endobj 505 0 obj << /S /GoTo /D (appendix*.101) >> endobj 508 0 obj (A. Algorithm 3 for generating Tag Systems: N-ary tag systems.) endobj 509 0 obj << /S /GoTo /D (appendix*.102) >> endobj 512 0 obj (B. Plots from Experiment 1) endobj 513 0 obj << /S /GoTo /D (appendix*.103) >> endobj 516 0 obj (C. Detailed Description of Four experiments on Tag Systems) endobj 517 0 obj << /S /GoTo /D [518 0 R /Fit ] >> endobj 520 0 obj << /Length 285 /Filter /FlateDecode >> stream xÚ]AKÄ0 ïý9ÎIÚ¦©7EEDA0ÄC¶ÛÝ t[ÙTeÿ½dÄK2L¿¼÷únlqyß(&;.$³&¥æhY5ojÅìú,\ï§-JÕðµ)Ìã7jp+?úå%1WôݸXÏ(+pJØ ûtûÞøaYI®JF<×u¼PvàI±Ë|ÀÒ¤'YÎM´]çù[Øù1²s?£Å?ÐǤäC^þ$áæD¥ZraÎ1ò/(7DºãàhHâ64Îý×Iuòm©!°m^¼"9Aôö =sé·TzÇÊFqiêà)ya5ü{KUç^+Ê0Fâο:o)endstream endobj 518 0 obj << /Type /Page /Contents 520 0 R /Resources 519 0 R /MediaBox [0 0 612 792] /Parent 526 0 R >> endobj 521 0 obj << /D [518 0 R /XYZ 88.936 688.12 null] >> endobj 522 0 obj << /D [518 0 R /XYZ 88.936 668.32 null] >> endobj 519 0 obj << /Font << /F52 525 0 R >> /ProcSet [ /PDF /Text ] >> endobj 529 0 obj << /Length 55 /Filter /FlateDecode >> stream xÚs áÒw35R04г´´TIS046Ö37³P0³°Ð34RIÖÈÌÔ ñâr á ò: endstream endobj 528 0 obj << /Type /Page /Contents 529 0 R /Resources 527 0 R /MediaBox [0 0 612 792] /Parent 526 0 R >> endobj 530 0 obj << /D [528 0 R /XYZ 133.768 688.12 null] >> endobj 527 0 obj << /Font << /F52 525 0 R >> /ProcSet [ /PDF /Text ] >> endobj 533 0 obj << /Length 1955 /Filter /FlateDecode >> stream xÚuIÏFô_á:H0KoH©ÔS-UUÕù5kp\ÿû¾ðy3óæíÛøóîÃǯq° MêG«Ýû*M7Y¯¶q¼ ý`µ+ÿ2»*ïÞ:ð3ó§ù¦¿xï~ýøu¬¬¿É²ïù«ulÂ(¤+xQdÎÞ:1µ·¶fô¬©»Ðئì½Ð7×W!Uá³øÆ ¼Ò£÷ï|ÙãÑeä±³g3ãÀÍËϯøf ( ý}Å»U.º^èñh67ÜLá\ÇGy*£6ÞÄíRw(¼kH\·Ç7l¬â2¾dÓæ·Âñ¦ûîm EÛ³Ê( æräÚ¬{J©#Ù8`ÿÐ,¯MòQïí²"TâaÊ;¯ËÍ¥ìÌ lÉ4ì;^£Ô¯ Zë]=$ZÖä`9h`|rÏB$®ÊKwöbßl¼udæ]ÙùM9KCú|GÌðªL¬BÊF%êyñYY2 "ª52Ë5ä(,Xd<åkáeÏÌ\¾ý óö' »ÿê\ÕíeìXp÷9àìäúû:%*qê/ ûû9tòþ8°zIJ÷ "6:3ViÄ+áLp¥Ö£yó´_½ÌÔçÎ$¯áe6¡ÏÍBsÍÑì¾ûï4¥ý0ðq{ã3 øl &%cèNFÜÆz¼Ns@si(È { ¾×¤ê³Og/MÀø¡ M©QÚÈ|A ¼V¸ù,$áhZqv¢a,µ»x5ÎP-¶sþ 4¢°¸|{)cßľpM}ABµî^x¯uh¢7qú1õ1ï{¤ä0Ä<çt=3RåC×321Csöæeå|/@àßfÇz%j1 @ujF<¥2,qJE%5(^NLÇ9:¡û¦>õLv¤¶É2¶zÔ¬¤í r92J rª;£©<À é2uAW2Õ ¼Qkµ ÓtJô]Ì'}q?ßKæÀâ¾»ä#4qºe_e|ÖâVa¬áòßä0:ï0Ýjít¸A½¬*UHL,úAîc(N¿pÍÖûRÄZ4Z· ÞÃïû<¬_xºì[tNæ ¿ÇZuÕíî»Ø§avZ1¡±L\¹(°ìhVF¡\@ÇÈz¹"Û^xµïÕ¤Åh~ãûHzäï½Áv´ ¨yUÞ?Q½F¹ûîæWÅ6%mT°©¡àà¥,àj¶ÚNZjB7^\{3`nØÏe¡3¹kÁ åß(qk²ÐÖNñOà Ú@JTÌBǹWµI\2=6M}×9ê:;LSðqHD@1gTs±Æ"85_fFÞ°_h$Ëáé qm ¢±(¡VÖ ¸R5SeAX¼BÝ>tu}³D¹öKýCJ)Þ9@ÇQÍëAÆhùìWQ÷÷o2fkY`s!«3µÜx¾;ó ».kÚìlp5Ñ%²hÇ uÍå¢ÆXÍE` ¶A8÷çYÂy\Ûj?SèÛ¯ÊÕIz6ɦWIYÎxøÂHBåG¨î^TR-¾ùìi ªõ(÷5H[mk¸1µ *¾°ROZVÌ·T3dÎâmû9ØRKHá:0¬ó¼?êø%ôJ9~{ïc$óÅV¾ó¸`É4>QõúLßø·¸x¥üX±âì#,ÑϽ RjåZÑ &bµqÔÈÔ§@û ØÇùÓ .I£5÷. uìztÏU¸òô`YZó³Gï2BnQÈ£ ´z÷À¶6tÚñìN3>´ZM<F#(º +7=R»ihKgç¥!½åD:¯ûN F9ó¢piÀ;ا3eÀèø¬«u÷ÄüDjæ@ Ñöüü~và2îÐqT£ /#@úãTôȵVßò yxŧ!óe³éQá$kÿqÁË¢Ó¾ñ@¬w xjzÞÊNÎn窸ãâEÕ$¥âÔð=r7Þ¼N °âéozLïeã®nËÛßßOÍXMÿûw!ò] Áú1Ñ8öLySZpQÓCøÅïÓ¸Ç:°´I&LÈè¾È 4õû»20ý/ei¼°Pô^¬A¼d Ô¨ÕG¡o'"7ÓÛѳ[é=,^> ·}{§8³ËôqþKõo$ÔÏóæø/³RñNpÚ¸Û¼.a(ÿ`ðk)0PÊEÉéE÷fR¬ì¹1þ(WP(6iòßSD¢Æó_vþì#'endstream endobj 532 0 obj << /Type /Page /Contents 533 0 R /Resources 531 0 R /MediaBox [0 0 612 792] /Parent 526 0 R >> endobj 534 0 obj << /D [532 0 R /XYZ 88.936 688.12 null] >> endobj 6 0 obj << /D [532 0 R /XYZ 88.936 668.32 null] >> endobj 531 0 obj << /Font << /F62 537 0 R /F52 525 0 R >> /ProcSet [ /PDF /Text ] >> endobj 540 0 obj << /Length 2631 /Filter /FlateDecode >> stream xÚYI㶾ϯhLV2IP\rg