Explaining Godel's Theorem: Intuitive Explanation w/o Math

In summary: TNT. That's because there's no way to make a statement in TNT that is both true and syntactically valid. So for example, the sentence "0=0" is not a statement in TNT, but it is a sentence in English.In summary, the Godel theorem states that any formal system that includes the natural numbers will contain self-referring sentences. These self-referring sentences lead to problems, which is the source of the Godel theorem. It is not possible to construct a logically consistent system that does not contain self-referring sentences.
  • #36
epenguin said:
?:confused: Does that mean you could have a finite machine that can prove any theorem within these systems in a finite time or have I confused issues?
Yes
epenguin said:
If not, why doesn’t someone make such a machine?:confused:
They have done so (although the applet mentioned in wikipedia doesn't seem to load properly)

epenguin said:
Anyway the problem I always had about multiplication is I could never see why it is said to be a separate fundamental operation like an axiom.:confused:
Multiplying n by m is just adding n to itself m-1 times! As far as I can see you could specify an algorithm involving just the notions that are in the numbers, succession etc., and addition - define multiplication within those axioms etc.. So if you can assume addition by my reasoning you would have the whole of arithmetic.
That you can do something m-1 times involves an assumption about the nature of m, so you're really introducing new axioms which are equivalent to those of multiplication

epenguin said:
But if I have missed something about multiplication, why is raising to a power, n^m being just multiplying n by itself m-1 times completely by the same form of definition as multiplication above, not also a fundamental independent operation or axiom?

Once you have multiplication you can define functions which need loops to program. For instance you can define exponentiation in terms of addition and multiplication as I mentioned previously
 
Physics news on Phys.org
  • #37
chronon said:
That you can do something m-1 times involves an assumption about the nature of m, so you're really introducing new axioms which are equivalent to those of multiplication



Once you have multiplication you can define functions which need loops to program. For instance you can define exponentiation in terms of addition and multiplication as I mentioned previously

Thank you, surprisingly I begin to see. When I program to add/subtract numbers I can do it without it having any meaning. E.g. Just add or remove strokes on a tape. Whereas when I said ‘do it m times’ I am attaching a meaning to a number.

I try to get round what this is assuming and make it a purely mechanical algorithm on the lines of codec9. The way I would naturally do it involves a cycle. You are saying a cycle is an idea additional to the simple addition-axioms only arithmetic, and that it can be defined as equivalent to multiplication. You are also saying cycle is inevitable if I want to multiply (less evident but I will think about it). So this primitive arithmetic has no cycles. I needed cycles for multiplication because I have a subroutine going that keeps track of the number of additions I have made, knocking 1 off a register and when that becomes 0 I stop my additions.

And there are no cycles in the dumbed-down addition arithmetic? If I try to prove A + B – A = B in general or for a particular case I am not going to have to go back to the first A when I write the second in order to know it’s the same thing?
 
  • #38
The magic at work here is that you can do string processing via integer arithmetic. We can encode information into the digits of a number, and the four basic (integer) arithmetic operations are sufficient to extract and manipulate that data, and are thus enough to implement any algorithm -- and first-order logic is powerful enough to let us reason about algorithms in Peano arithmetic.



For your particular question, you only need recursion, and we don't have to fully implement a Turing machine to make use of it. I'll give you a hint and let you mull it over for a bit, and you can ask for more. I've colored the hint white, so you'll have to highlight it to see it:

__________________________________
Notice the 6-digit base-67 number
64,32,16,8,4,2​
has some interesting properties...

(I've written the individual digits in base 10, and separated them with commas)
__________________________________
 
Last edited:
  • #39
I will be away for a time, mulling and other things. Back later.:smile:
 
Back
Top