What does the Incompleteness Theorem imply?

[TVAA]

GIT shows that [simplify simplify] any finite system capable of representing arithmetic will always have “holes” in it – possible statements/configurations that it can never reach.

Any system that can be considered to be emulated by basic physics (which we know from experience is more than capable of generating arithmetic) must therefore have the same limitation. Therefore there will always be a way to interact with that system in a way it’s not capable of handling. . .

[FranticMad]

Going back to the OP, let’s take it one step at a time. Consider the first assertion:

Godel’s Incompleteness Theorem does not imply that humans will always be smarter than computers.

Does anyone disagree with that first point?

[begbert2]

TVAA, are you aware that Turing machines are theoretical constructions? (They haven’t quite got the infinitely long tape memory thing figured out yet.) So, I’ve never seen a Turing machine, you’ve never seen a Turing machine, and natural law has never laid a finger on a Turing machine. So, that “weakness” is out of the picture.

Turing machines are defined with a specific input alphabet; The only variety in input allowed is the ordering of the input symbols, not what these symbols are. So that “weakness” is out of the picture.

It would be relatively simple to make a turing machine that would solve most problems, and always halt; just have it simulate a universal turing machine but only run it for N steps. After N simulated steps, it halts, period. It doesn’t always find the answer for you, but it would always halt. So the threat of freezing is also out of the picture.

Godel says that not all questions can be answered, even by following the rules. Not that such a failure to be able to answer will bother the system one bit.

Godel’s Incompleteness Theorem does not imply that humans will always be smarter than computers.

No, that’s fine. GIT implies nothing about relative intelligence levels of things, or their relative ‘vulnerability’ to input. Just their potnential completeness.

[lucwarm]

A little off-topic, but I would add that the “halting problem” also does not imply that humans will always be smarter than computers.

And if you think you can look at a computer program and always know in a finite amount of time whether it will halt, you’re kidding yourself.

And these hand-waving arguments are freaking annoying.

[Spiritus_Mundi]

TVAA

The physical laws governing the behavior of those circuits is more than sufficiently complicated for the Theorem to apply.

Can you demonstrate that please. Or is it simply your untested conviction that it must be true?

I am more than willing to accept that pocket calculators can be made essentially failure-proof for a limited set of possible inputs, but there are many more possible interactions with the material making up the device than any designer could anticipate.

This has nothing to do with GIT.

GIT is a theorem about abstract constructions (proofs). You are talking about physical and material tolerances. The two things are not related.

I have a coin in my pocket. Flipping the coinc generates a psuedo-random binary value. This system, however, can fail if both the coin and I are incinerated in a nuclear blast. This has nothing whjatsoever to do with GIT.

To repeat myself: Will you next explain how a consequence specifically tied to the evaluation of Godel statements restricts a calculator when, “Calculators’ circuitry does not include the algorithms for evaluating Godel numbers?” You might also explain how that quoted statement (made by you) coexists with the quoted statement at the top of this post. In other words:
[ul][li]If the circuitry does not inlude the algorithms for evaluating Godel numbers, then how is that circuitry sufficiently complicated for the theorem to apply?[/ul][/li]

GIT shows that [simplify simplify] any finite system capable of representing arithmetic will always have “holes” in it – possible statements/configurations that it can never reach.

No, it doesn’t.

Simplifying doesn’t lead to understanding if you drop a crucial requirement for the theory to hold. GIT limits axiomatizations of arithmetic. Unless your calculator generates proof of arithmetic theorems, GIT places no limits on that calculator’s behavior.

Any system that can be considered to be emulated by basic physics (which we know from experience is more than capable of generating arithmetic) must therefore have the same limitation.

Prove it.
FranticMad

Godel’s Incompleteness Theorem does not imply that humans will always be smarter than computers.

How could it? Whatever limitations GIT places on computers, because they can model a peano axiomatization, would also apply to humans, because they can model a peano axiomatization. (Neither, of course, places any limits on capacities not strictly bound by a Peano axiomatization.)

Then, of course, there’s the slight little matter of GIT saying nothing whatsoever about intelligence.

[ultrafilter]

*Originally posted by TVAA *
The physical laws governing the behavior of those circuits is more than sufficiently complicated for the Theorem to apply.

Any system that can be considered to be emulated by basic physics (which we know from experience is more than capable of generating arithmetic) must therefore have the same limitation. Therefore there will always be a way to interact with that system in a way it’s not capable of handling. . .

No matter how many times you repeat this, it won’t come true. Have you even read the theorem?

[erislover]

I am haunted by the ghost of my old thread, eh ultrafilter? I wish to thank you again for your posts there (and here).

[FranticMad]

So let’s assume we agree on the OP’s first assertion, that GIT does not imply that humans will always be smarter than computers.

So the next assertion of the OP is:
It does mean that no finite system can ever derive all truths. Is this consistent with GIT? Is it a trivial or a provable statement?

Next assertion was:
**No computer can be made that cannot be crashed. ** I think this is where some logic is missing, or some assumptions are unstated.

TVAA keeps making assumptions about the equality of physics, number theory, Universal Turing Machines, and calculators. I am not a professional mathematician, so I am having some trouble following what the connections are.

In addition, he says the universe does not do computation because it has no input or output (a statement that contains so many debatable, but unstated, assumptions that it is nearly meaningless to my limited intelligence).

If I am catching TVAA’s drift, he is saying that:

1. Since mathematics and physics are the same, and
2. GIT shows that mathematics is incomplete, then
3. Physics is incomplete, and
   3a)* [add missing assumptions here]*, therefore.
4. Any computer [undefined] will crash [undefined] because it is built from physics [undefined] and math [defined as the math considered by GIT].
5. Q.E. non-D.

Aside from that, I don’t know what TVAA is trying to say – i.e. what the point of his argument is. Perhaps someone can enlighten me.

[ultrafilter]

*Originally posted by FranticMad *
So let’s assume we agree on the OP’s first assertion, that GIT does not imply that humans will always be smarter than computers.

That’s a safe assumption.

**

So the next assertion of the OP is:
It does mean that no finite system can ever derive all truths. Is this consistent with GIT? Is it a trivial or a provable statement?**

Any inconsistent system can derive all truths, as well as all falsehoods. Getting a system that can prove all truths and nothing else is impossible, although GIT itself does not prove that.

**

Next assertion was:
**No computer can be made that cannot be crashed. ** I think this is where some logic is missing, or some assumptions are unstated. **

Yeah, something like that.

**

TVAA keeps making assumptions about the equality of physics, number theory, Universal Turing Machines, and calculators. I am not a professional mathematician, so I am having some trouble following what the connections are. **

I am a mathematician (although not professional). It’s a total mystery to me too.

**

In addition, he says the universe does not do computation because it has no input or output (a statement that contains so many debatable, but unstated, assumptions that it is nearly meaningless to my limited intelligence).**

There’s no reason why we, part of the universe, can’t interpret the actions of the universe as computation. I don’t choose to do so, but to each his own.

**

If I am catching TVAA’s drift, he is saying that:

1. Since mathematics and physics are the same, and
2. GIT shows that mathematics is incomplete, then
3. Physics is incomplete, and
   3a)* [add missing assumptions here]*, therefore.
4. Any computer [undefined] will crash [undefined] because it is built from physics [undefined] and math [defined as the math considered by GIT].
5. Q.E. non-D.

Aside from that, I don’t know what TVAA is trying to say – i.e. what the point of his argument is. Perhaps someone can enlighten me. **

Don’t look at me.

[ultrafilter]

Just to make sure that everyone’s on the same page, I’m restating GIT from this thread. The explanations of all the terms I use are at the bottom of the second page of that thread.

All right, I’m gonna give this a shot. What I’m presenting is a modern statement of the Gödel-Rosser theorem, a generalization of Gödel’s original theorem (more on this later). I’ll begin with a basic set of symbols, state the theorem, and go into detail as to what the conditions mean. In all that follows, all lower-case variables represent non-negative integers. Italic capital letters (like G) will denote sentences. Capital letters (like K) will denote theories. Of course, any exceptions will be noted.

I think we all know that ’ denotes the successor function (i.e., 0’ is the successor of zero). What the successor function is not specified, it just has to be defined for zero. n is used to denote the nth successor of zero.

Symbols

We say x < y if there is a number z such that x + z = y.

|–[sub]K[/sub] G means that there is a proof in theory K of the sentence G.

Lastly, != will be used to mean “not equal to”. I imagine everyone knows that, but I just thought I’d throw it out for clarity.

And just for ease of my typing, V will represent the logical “or”.

Universal quantifiers on free variables will be assumed. This is a standard convention among logicians.

The Theorem

So here are the conditions for the Gödel-Rosser theorem. Let K be a theory with equality in the language L[sub]A[/sub] that satisfies the following:[ol][li] K has a recursive axiom set.[/li][li] |–[sub]K[/sub] 0 != 1.[/li][li] Every recursive function is representable in K.[/li][li] |–[sub]K[/sub] x < n [symbol]®[/symbol] x = 0 V x = 1 V … V x = n[/li][li] |–[sub]K[/sub] x < n V n < x[/ol]Then, if K is consistent, an undecidable sentence R exists in K.[/li]
Initial explanations

All right, so there’s a lot of jargon in there. Where to begin? I’m not going to go into all the detail, just enough that you can do something with that statement other than stare at it googly-eyed.

A theory with equality is just a theory that has a predicate “=” which is reflexive, symmetric, and transitive. There’s that.

L[sub]A[/sub] is the language of arithmetic. It has the predicate “=”, the constant 0, the successor function, and functions for addition and multiplication (not necessary, but what the heck, we’ll use 'em). And that’s all you can talk about.

I’ve already explained what “consistent” means, but just for ease of reading, a theory is consistent if there is some sentence which is not a theorem of that theory.

Condition 1

K has a recursive axiom set iff the function Pr: N -> 2 defined as Pr(y) = “y is the Gödel number of a proper axiom of K” is recursive. A proper axiom is one that the theory has in addition to the basic axioms of predicate calculus (which could be any old axiom, if you take the right formulation of predicate calculus). I’ll write about recursive functions later–look it up on Mathworld if you like, but realize that they use a slightly different definition from the one I use. I think they’re equivalent, but I haven’t shown that.

Condition 2

I think we’re good on this. Let me know if we’re not.

Condition 3

A recursive function f of n functions is representable in a theory K iff there’s a wff (sentences are wff’s with no free variables) B(x[sub]1[/sub], …, x[sub]n[/sub], y) such that[ol][li] If f(k[sub]1[/sub], …, k[sub]n[/sub]) = m, then B(k[sub]1[/sub], …, k[sub]n[/sub], m)[/li][li] |–[sub]K[/sub] ([symbol][/symbol][sub]1[/sub]y)*B*(k[sub]1[/sub], ..., k[sub]n[/sub], y)[/ol]The subscripted existential quantifier ([symbol][/symbol][sub]n[/sub]y) means “there exist exactly n distinct y’s such that…”[/li]
Condition 4

Pretty self-evident, I hope.

Condition 5

Again, this should be pretty straightforward.

[Spiritus_Mundi]

Any inconsistent system can derive all truths, as well as all falsehoods. Getting a system that can prove all truths and nothing else is impossible, although GIT itself does not prove that.

Well, I think we can give this one to GIT by assuming that some of the unproveable theorems in a Peano axiomatization are, in fact, true. Obviously, GIT does not guarnatee this (being unconcerned with soundness), but I don’t think it is a horrible assumptive leap to make.

[ultrafilter]

*Originally posted by Spiritus Mundi *
**Well, I think we can give this one to GIT by assuming that some of the unproveable theorems in a Peano axiomatization are, in fact, true. Obviously, GIT does not guarnatee this (being unconcerned with soundness), but I don’t think it is a horrible assumptive leap to make. **

“unproveable theorems” aside (;)), any theory with undecideable statements has some true and some false–the negation of an undecideable statement is itself undecideable.

[Spiritus_Mundi]

Yes, but I assumed that your objection to allowing GIT to imply that no consistent system can prove all truths lay in the soundness of the axioms. GIT says nothing at all about “truth”, just what is proveable given a specified axiomatic base.

It seems you meant something else. I guess I should just say:

[ultrafilter]

*Originally posted by Spiritus Mundi *
**Yes, but I assumed that your objection to allowing GIT to imply that no consistent system can prove all truths lay in the soundness of the axioms. GIT says nothing at all about “truth”, just what is proveable given a specified axiomatic base.

It seems you meant something else. I guess I should just say: **

If every statement that’s true about a system is provable, the theory of that system is complete. GIT says some consistent systems are incomplete, meaning that there are true statements which are not proveable. Make sense?

[Spiritus_Mundi]

Yes, but you said: Getting a system that can prove all truths and nothing else is impossible, although GIT itself does not prove that.

Unless “prove all truths and nothing else” is not being used as a description for “consistent and complete” then it would seem that GIT does prove that.

And that seems to be th e sense of your last post, too. GIT impies that some true statemnets will always be unprovable.

[ultrafilter]

I think I’m not being entirely clear, and that we’re arguing past each other. Everything you just said is entirely correct.

[Spiritus_Mundi]

Okay. I’ll chalk it up to a big mutual wooosh.

The important thing is that we all agree TVAA** is wrong.

[Spiritus_Mundi]

And that Spiritus Mundi can’t type, of course.

But that has long been proven beyond dispute.

[TVAA]

Wow. I leave the boards for a few hours, and this happens…

I’ll try to get around to responding to your posts ASAP.

In the meantime: Spiritus: I am generally awestruck by the levels of rationality and intelligence you demonstrate in your posts, and I disagree respectfully with your contentions in this thread, but I simply cannot account for your question about whether the physical world is sufficiently complex to model arithmetic.

Are we using utterly different meanings of words? That’s the only way I can account for your question – if I take it at face value, it seems utterly foolish.

Isn’t it obvious that the reality underlying the “physical world” is more complex than basic mathematics? If it were less, how could the world follow arithmatic principles? How could a device be designed that follows them – for that matter, how could anything follow them?

[ultrafilter]

*Originally posted by TVAA *
Are we using utterly different meanings of words? That’s the only way I can account for your question – if I take it at face value, it seems utterly foolish.

Yes. “Model” means something very different here than what you seem to think it means.