[FOM] QUESTION ABOUT COMPUTERS

[John McCarthy]

A computer program can examine itself unless special means are taken
to prevent it.  Many bugs can be found that way, although I don't
think it is customary.  For example, it might detect by looking at
itself conditions it would divide by zero and could find the simpler
kinds of infinite loops.  Neither Turing's nor Godel's results say
anything to the contrary.

What a computer cannot have is a program that will always decide
whether a version of itself somehow provided with infinite memory (say 
by asking an operator to mount another tape) will ever halt.  Programs 
that sometimes answer the question are possible, but Turing proved
that a program that will always answer correctly cannot exist.

There is a finite version of Turing's result.  We can write a program
D that given another program P, and input for it, and a number n, will
answer correctly whether the program with the given input will halt in
no more than n steps.  The finite version of Turing's undecidability
theorem says that D cannot always give an answer in much less than n
steps.  The proof is an adaptation of Turing's.  We can convert such a
fast D into a program D' that answers whether D' itself will halt in
enough less than n steps and then do the reverse of what it predicts
about itself.