The Geek Atlas by John Graham-Cumming

Author:John Graham-Cumming
Language: eng
Format: epub, pdf
Tags: ISBN: 978-0-596-52320-6
Publisher: O'Reilly Media
Published: 2009-06-15T16:00:00+00:00

Equation 66-1. The Halting Function

Equation 66-2. The Diagonal Function

g(i) only has one parameter, i, which is just a number. It is used by h(i,i) to find both the program numbered i and the input numbered i. And g(i) is 0 if the program numbered i does not halt with input i; otherwise, g(i) is undefined. Now for the mind-bending bit. Suppose that there is a computer program for h(p,i). It’s fairly easy to see two things:

1. There must be a program for g(i) because it is defined in terms of h(p,i).

2. g(i) is computed by the program number j for some number j.

So what happens if you try to calculate g(j)? What happens if we feed g(j) to itself?

1. If g(j) is 0, then it means that h(j,j) is 0, which means that program j does not halt with input j. But program j is the program for g(j) , which we’ve just said is 0. This is contradictory, and hence g(j) cannot ever be 0.

2. If g(j) is undefined, then it means that h(j,j) is 1, which means that program j does halt with input j. But program j is the program for g(j), which we’ve just said is undefined (doesn’t halt). Another contradiction.

This reasoning leads to contradictions and means that the original assumption was incorrect: there is no program to compute h(p,i). The Halting Problem was significant because it showed that Turing’s Machines could not be used to solve important unsolved mathematical problems.

It also tells us that no computer is going to be able to predict whether a program will stop responding. So at least we humans aren’t totally out of a job when it comes to debugging.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.