HOWTO Understand and Appreciate the Halting Problem

Martin Rodgers

Revision History
Revision 0.012003-01-22Revised by: mcr
Created basic SGML file.
Revision 0.022003-02-04Revised by: mcr
Fixed a few bugs. Added some more text (More practice than theory). Added some code! (Hacking the Halting Problem & Hacking Uncertainty) Added an outline for Virtual Machines. Added an outline for Appreciate the Problem.
Revision 0.032003-02-06Revised by: mcr
Added some more text to the outline for Virtual Machines. Added some more text to the outline for Appreciate the Problem.
Revision 0.042003-02-10Revised by: mcr
Retitled various sections. Minimal changes to structure and text.
Revision 0.052003-02-16Revised by: mcr
Added the Familiar Ground section (unspecified behaviour in ANSI C etc) Retitled various sections. (Was: Introduction / More practice than theory / More theory than practice / Appreciate the Problem / Conclusion / References: books References: links). Small changes to structure and text.
Revision 0.062003-02-26Revised by: mcr
Added the "An open question" subsection to the "Appreciate the Problem" section.
Revision 0.072003-03-25Revised by: mcr
Added "An Invitation to Algorithmic Information Theory" to the links appendix. Added "The Emperor's New Mind" to the books appendix.
Revision 0.082003-03-27Revised by: mcr
Added "EFF DES Cracker Project" to the links appendix. Added Ross Anderson's homepage to the links appendix. Added Rudy Rucker's homepage to the links appendix. Added id tags to book and links entries.
Revision 0.092003-03-31Revised by: mcr
Added a skeleton section on process automation. Added a skeleton section on security. Added some flesh to the spam and crypto sections.
Revision 0.102003-04-01Revised by: mcr
Added RFC3514 to the links appendix.
Revision 0.112003-04-17Revised by: mcr
Added a little bit (Turing Complete) to appreciation/security. Changed title for appreciation from "Appreciate the Problem" to "Appreciating the Problem". Added a theory section, with turing/turingcomplete/turingequiv subsections. Only a skeleton so far. (Turing is looking a bit thin!)
Revision 0.122003-04-20Revised by: mcr
Added a counting subsection (Counting haltable programs) to the problem (The halting problem) section. Added a physicallimits (Physical Limits) subsection the problem section.
Revision 0.132003-04-21Revised by: mcr
Added the omega (Omega Probability) subsection the problem section.
Revision 0.142004-02-26Revised by: mcr
Added the hourglass subsection the appreciation section. Added 2004 to the copyright.

Table of Contents
1. Introduction
1.1. Copyright Information
1.2. Disclaimer
1.3. New Versions
1.4. Credits
1.5. Feedback
1.6. Translations
2. More practice than theory
3. Familiar ground
3.1. Hello, World
4. Halting
4.1. Goodbye, World
4.2. Foo
4.3. Testing for Haltable Functions
4.4. A conservative test
4.5. Testing the Standard C Functions
4.6. A little uncertainty
4.7. Bar
4.8. Paradox
5. Machines
5.1. Machines are Numbers
5.2. Countable Sets
5.3. Uncountable Sets
6. The Halting Problem
6.1. Counting haltable programs
6.2. Physical limits
7. The Church/Turing Thesis
7.1. Turing
7.2. Turing Complete
7.3. Turing Equivalence
7.4. The Omega Probability
8. Appreciating the Problem
8.1. The hourglass
8.2. An open question
8.3. Cryptography
8.4. Security
8.5. Fighting Spam
8.6. Automation
9. Conclusion
A. References: books
B. References: links

1. Introduction

1.3. New Versions

This is a work in progress.

The latest version number of this document can be found in the HOWTO section of my homepage.

The newest version of this HOWTO will always be made available on my website, in a variety of formats: