- #1

bhobba

Mentor

- 10,124

- 3,251

Hi All

I normally post on the QM forum but also have done quite a bit of programming and did study computer science at uni. I have been reading a book about Ramanujan and interestingly he was also good friends with Bertrand Russell. You normally associate Russell with philosophy but in fact at Cambridge was 7th wrangler (Hardy was 4th and Littlewood 1st). The only thing guaranteed to get Russell away from philosophy was to discuss math which he did with relish with Ramanujan. He was finishing his second volume of principia mathematica and it got me thinking could Ramanujan have come up with Godel's theorem.

So I started looking into it. I have seen proofs before - but could they be simple so as to be clear and easily explained. After thinking and reading a bit I came up with one I will post - no claim of originality - a bit from here - a bit from there. BUT the interesting thing was if it was to be simple you really needed computing concepts which would not have been available at that time. I was sort of gobsmacked - it really requires our modern era to see it clearly and simply.

Anyway here is my computer science proof. Let f(x) be a function from the natural numbers to either 0 or 1. I will call them f functions. Obviously anyone can write computer programs for at least a few such functions. We will call such functions computable ie those that you can write programs for. The are at least a countable infinity of them because if x is any integer let f(x) = 1 when x is some integer n and 0 otherwise eg the for n=6, function f(x) is 0 except when its 6, then its 1. Now are all computable f functions a countable infinity? Well all computer programs are countable because they use a finite number of characters and are of finite length. So computable functions are a countable infinity. Assume this countable infinity is ordered in correspondence to the natural numbers 1, 2, 3 ....., n, .........

Ok are all f functions computable? As you will see that is the real key to Godel. Let g(i) = 1 - fi(i) where fi is the ith function in the ordering above. Now suppose g is computable. If so we can find it in the list of computable functions - say it is number k. So g(k) = 1 - fk(k). If fk which is the same as gk is 1 or 0 it says gk is the opposite - contradiction. So we have come up with a very interesting computer science result - there are non computable functions. Strange but true.

But wait for it - we have proved more - in fact Godel's theorem. Here is why. Let g(x) = 1 or g(x) = 0 be called a g statement. Obviously a g statement, in a consistent system, should be true or false. So lets assume all g statements are true or false. Ok suppose we have some logical system - you know those formal systems that have symbols like =, ∀, Γ and so forth. Lets input some natural number x. Suppose we have a program that generates all possible statements in that formal system. We check if its a proof of the g statements g(x) = 1 and then g(x) =0. Suppose the answer is yes on one of them. We output the g(x) = 0 or 1 depending on what has been proven true ie if the statement is g(12) = 1 we output g(12) = 1. If not a true g statement proof we check if its false. If false we output the opposite because we have assumed its consistent ie if it proved g(12) = 1 is false we output g(12) = 0. We stop when something is output.

See the problem - we cant compute g - but the above is a way to do it for any x if the assumption is true ie g statements are either true or false - that is if it terminates. Contradiction. The premise is false - there are undecidable statements in a system powerful enough to contain arithmetic. Suppose it never terminates - then you have the same issue - you cant decide if its true or not.

Interesting isn't it. This was a very famous theorem. But computing concepts makes it fairly easy to understand and along the way we have seen you have functions that can't be computed and that leads to Godel's famous result.

Or maybe I have goofed .

Thanks

Bill

I normally post on the QM forum but also have done quite a bit of programming and did study computer science at uni. I have been reading a book about Ramanujan and interestingly he was also good friends with Bertrand Russell. You normally associate Russell with philosophy but in fact at Cambridge was 7th wrangler (Hardy was 4th and Littlewood 1st). The only thing guaranteed to get Russell away from philosophy was to discuss math which he did with relish with Ramanujan. He was finishing his second volume of principia mathematica and it got me thinking could Ramanujan have come up with Godel's theorem.

So I started looking into it. I have seen proofs before - but could they be simple so as to be clear and easily explained. After thinking and reading a bit I came up with one I will post - no claim of originality - a bit from here - a bit from there. BUT the interesting thing was if it was to be simple you really needed computing concepts which would not have been available at that time. I was sort of gobsmacked - it really requires our modern era to see it clearly and simply.

Anyway here is my computer science proof. Let f(x) be a function from the natural numbers to either 0 or 1. I will call them f functions. Obviously anyone can write computer programs for at least a few such functions. We will call such functions computable ie those that you can write programs for. The are at least a countable infinity of them because if x is any integer let f(x) = 1 when x is some integer n and 0 otherwise eg the for n=6, function f(x) is 0 except when its 6, then its 1. Now are all computable f functions a countable infinity? Well all computer programs are countable because they use a finite number of characters and are of finite length. So computable functions are a countable infinity. Assume this countable infinity is ordered in correspondence to the natural numbers 1, 2, 3 ....., n, .........

Ok are all f functions computable? As you will see that is the real key to Godel. Let g(i) = 1 - fi(i) where fi is the ith function in the ordering above. Now suppose g is computable. If so we can find it in the list of computable functions - say it is number k. So g(k) = 1 - fk(k). If fk which is the same as gk is 1 or 0 it says gk is the opposite - contradiction. So we have come up with a very interesting computer science result - there are non computable functions. Strange but true.

But wait for it - we have proved more - in fact Godel's theorem. Here is why. Let g(x) = 1 or g(x) = 0 be called a g statement. Obviously a g statement, in a consistent system, should be true or false. So lets assume all g statements are true or false. Ok suppose we have some logical system - you know those formal systems that have symbols like =, ∀, Γ and so forth. Lets input some natural number x. Suppose we have a program that generates all possible statements in that formal system. We check if its a proof of the g statements g(x) = 1 and then g(x) =0. Suppose the answer is yes on one of them. We output the g(x) = 0 or 1 depending on what has been proven true ie if the statement is g(12) = 1 we output g(12) = 1. If not a true g statement proof we check if its false. If false we output the opposite because we have assumed its consistent ie if it proved g(12) = 1 is false we output g(12) = 0. We stop when something is output.

See the problem - we cant compute g - but the above is a way to do it for any x if the assumption is true ie g statements are either true or false - that is if it terminates. Contradiction. The premise is false - there are undecidable statements in a system powerful enough to contain arithmetic. Suppose it never terminates - then you have the same issue - you cant decide if its true or not.

Interesting isn't it. This was a very famous theorem. But computing concepts makes it fairly easy to understand and along the way we have seen you have functions that can't be computed and that leads to Godel's famous result.

Or maybe I have goofed .

Thanks

Bill

Last edited: