Schrodinger's Cat of Programming (or My understanding of Godel's Theorem)

Little Schemer deals with a few mathematical theorems through simple examples. It has an easily understandable explanation of Godel's incompleteness theorem. Eventhough the book primarily focusses on recursion, at one point it addresses the problem of infinite recursion. It happens only for partial functions for which you cant have a definite exit criteria.

Consider the list (6 2 4 jerry 5 7 3) and the atom jerry. If your objective is to locate jerry by tracing from the first location, you will traverse like this:
[1] -> [6] -> [7] -> [3] -> [4] -> jerry

Its not always guaranteed to end. Now lets try another:
Consider the list (7 1 2 jerry 5 6 3)
[1] -> [7] -> [3] -> [2] -> [1] -> [7] -> [3] -> [2] -> [1] -> [7].........

Wait, this will never end. Tom will never find Jerry if he uses your function. Such functions are called partial functions and functions which always return a value like factorial are called total functions.

Now let's say you want to write a function that takes a function and determines if the function will stop execution or not. In functional programming languages, you can pass functions as first class variables. It'll look like this:

(define will-stop?
(lambda (fun)
...))

Let's assume that such a function is possible (Assume is a revealing word from mathematical induction and i guess i might have spoiled the suspense already)

Now we have a function to test. Lets call it try

(define try
(lambda(x)
...))

Now just for fun, lets write a function, which is guaranteed to never stop. Let's call it wont-stop

(define wont-stop
(lambda (x)
(wont-stop x)))

Now before passing try to will-stop?, lets implement try

(define try
(lambda (x)
(and
(will-stop? try)
(wont-stop x)
)))

Lets assume that will-stop works for try and returns true, which means try will stop. try evaluates to

(and true (wont-stop x))

which wont stop. Now that contradicts with the assumed output of will-stop?

Now lets assume that will-stop works for try and returns false, which means try will never stop. try evaluates to

(and false (wont-stop x))

which returns false. Effectively try has stopped when the assumed will-stop? predicted try will never stop.

Now the only possible explanation of this anomaly or paradox is that will-stop? can never be implemented.(Connect the dots because i'm still connecting).This is the essence of Godel's incompleteness theorem.

One book which is gathering dust in my bookshelf and i hope will have a better explanation of Godel's theorem is Godel, Escher and Bach. Another series of books which i have heard always culminates in an explanation of Godel's theorem using logical unsolvable puzzles are Raymond Smullyan's puzzle books. Until i get any of Smullyan's books, i found an explanation of Godel's theorem for dummies here.

Schrodinger's cat is a thought experiment in quantum mechanics which is equally bizzare. Imagine that we have a cat in a box and a GM counter which is triggered by an atom which may or may not decay. GM counter controls a hammer which shatters a flask of cyanide which might kill the cat. Now if you come back after an hour, the cat in the box may be alive or dead or both and you would never know until you actually open the box. The cat is in a half-dead,half-alive state and continues to have a superposition of multiple histories/states until the box is opened, when it becomes either dead or alive.

Back to our previous finding, For try, will-stop? wont stop if we assume will-stop? (try) will stop and will-stop? will stop if we assume will-stop? (try) wont stop.Now thats a paradoxical statement which makes Schrodinger's cat sound like simple probability.