"The first incompleteness theorem states that no consistent system of axioms whose theorems can be listed by an effective procedure (i.e., an algorithm) is capable of proving all truths about the arithmetic of natural numbers. "
Doesn't it follow that you can't write a program that proves all the true things about natural numbers. Therefore there will be true facts about the arithmetic of natural numbers not derivable from the axioms. That's my reading of it.
Basically there will be formulas, you can't get to by following an algorithm from the axioms. But if you lets say randomly stumble on a formula, you can easily prove it works or not.
That's my reading of it.
So for example, we can't write a program that will find all formulas, like for example.
a^2 + b^2 = c^2
But once we have a formula, we can prove that this formula works.
Thats my understanding of this Theorem. Correct me if I'm wrong.
You certainly can't write a state machine for the halting problem either.
i can extrapolate even further and say that everything is a state machine. humans are a state machine, plants are a state machine, reality itself is a state machine.
we don’t see it like this because of the sheer complexity, but in the end we are a continuous computation that occurs at every moment in time.
Godel incompleteness applies for math, logic, etc but you need to understand that math is human construct. formulas and numbers don't exist in a void. they need a substrate like a human mind or a computer.
Also by state machine i mean a system is basically a current state + state transitions. I was not using state machine as a way of modeling and solving a problem. That's a narrow definition of a state machine only applicable within a certain domain.
so everything in reality can be seen as a state machine
also as an orthogonal side note to the the halting problem: in theory you may conceive of systems and/or programs that will never halt but remember they are theoretical. Eventually, entropy gets to us all so for anything, even ideas of algorithms that may never halt, is temporary and are guaranteed that given enough time they will halt.
Comments
"The first incompleteness theorem states that no consistent system of axioms whose theorems can be listed by an effective procedure (i.e., an algorithm) is capable of proving all truths about the arithmetic of natural numbers. "
Doesn't it follow that you can't write a program that proves all the true things about natural numbers. Therefore there will be true facts about the arithmetic of natural numbers not derivable from the axioms. That's my reading of it.
Basically there will be formulas, you can't get to by following an algorithm from the axioms. But if you lets say randomly stumble on a formula, you can easily prove it works or not.
That's my reading of it.
So for example, we can't write a program that will find all formulas, like for example.
a^2 + b^2 = c^2
But once we have a formula, we can prove that this formula works. Thats my understanding of this Theorem. Correct me if I'm wrong.
You certainly can't write a state machine for the halting problem either.
so my original claim was that:
Godel incompleteness applies for math, logic, etc but you need to understand that math is human construct. formulas and numbers don't exist in a void. they need a substrate like a human mind or a computer.
Also by state machine i mean a system is basically a current state + state transitions. I was not using state machine as a way of modeling and solving a problem. That's a narrow definition of a state machine only applicable within a certain domain.
so everything in reality can be seen as a state machine
also as an orthogonal side note to the the halting problem: in theory you may conceive of systems and/or programs that will never halt but remember they are theoretical. Eventually, entropy gets to us all so for anything, even ideas of algorithms that may never halt, is temporary and are guaranteed that given enough time they will halt.