Possible counter-example to Church Turing Thesis

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Prelates, Moderators General

Possible counter-example to Church Turing Thesis

Postby tomtom2357 » Mon Apr 02, 2012 1:40 pm UTC

For those who haven't heard of the church-turing thesis, here is the main idea: a turing machine can compute anything computable by an algorithm. My idea for a possible counter-example to this would be a turing machine that can change its own code, so in addition to the state transitions, it also has additional code that can change its own (or another state's) code. Could this be a counter-example?
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.
tomtom2357
 
Posts: 556
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Possible counter-example to Church Turing Thesis

Postby gametaku » Mon Apr 02, 2012 2:52 pm UTC

No. Your replacing the Turing machine with a device of your own, and claiming it as counter example the Church Turing Thesis.

A counter example would require you to find something that is commutable by an algorithm, and prove that the turning machine could not compute it.
gametaku
 
Posts: 149
Joined: Tue Dec 30, 2008 2:21 am UTC

Re: Possible counter-example to Church Turing Thesis

Postby Yakk » Mon Apr 02, 2012 3:24 pm UTC

Universal Turing machines are pretty simple to program. They have the program of a Turing machine on one of their tapes, and run on another.

Adding more tapes to a Turing machine doesn't make it more powerful. It is known.

Such a Turing machine (a UTM) is constructed to demonstrate that we can run any alternative TM on it. Extending it so that it can write to the tape it has its program on does not make it more powerful. It is known.

Your system, a Turing machine that can change its own program, is no more powerful than a UTM with the ability to modify the program tape. It is known.

As to your question (could this be a counter example?), no, it cannot be. On top of the fact that your given example is wrong, you do not know enough to come up with such a counter example at this point. If you where to stumble upon a Church-Turing thesis counter example, you wouldn't even be able to express what you stumbled upon and/or recognize it. Look up the Dunning-Kruger effect. This applies to your situation.

The proper question in your state of knowledge isn't "could this be a counter example?", but rather "where did I go wrong?"
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10427
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Possible counter-example to Church Turing Thesis

Postby WarDaft » Mon Apr 02, 2012 10:31 pm UTC

Not to mention that there's no evidence that the operations of neurons aren't computable by a Turing machine as well (by less in fact, but we don't need that for this particular case) so there is considerable reason to believe that any operation you can conceive of can be represented on a TM's tape, and that it can do everything with that operation that you actually can. This likely holds even if there are (and it's believed there aren't) quantum operations harnessed as part of natural though processes.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
User avatar
WarDaft
 
Posts: 1574
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Possible counter-example to Church Turing Thesis

Postby Goplat » Tue Apr 03, 2012 6:05 pm UTC

WarDaft wrote:Not to mention that there's no evidence that the operations of neurons aren't computable by a Turing machine as well (by less in fact, but we don't need that for this particular case)
Actually, there is: Neuron-based life forms have been observed in rare cases to exhibit intelligence. (Since it appears you tend to hang out with Yudkowskybots, it's understandable you might not be aware of this.)

there is considerable reason to believe that any operation you can conceive of can be represented on a TM's tape
So "does this program halt or not" is inconceivable? I don't think that word means what you think it means.
and that it can do everything with that operation that you actually can.
OK, I'm not going to try to prove that I can solve the halting problem in the general case (even if I can, it would take infinitely long to demonstrate), so here's a different problem: let's see a Turing machine and input tape to generate secure 128-bit symmetric encryption keys, something I can do quite easily. (If it generates the same key every time, that's not secure).
Goplat
 
Posts: 490
Joined: Sun Mar 04, 2007 11:41 pm UTC

Re: Possible counter-example to Church Turing Thesis

Postby EvanED » Tue Apr 03, 2012 6:24 pm UTC

Goplat wrote:here's a different problem: let's see a Turing machine and input tape to generate secure 128-bit symmetric encryption keys, something I can do quite easily. (If it generates the same key every time, that's not secure).

That's not really fair. It's somewhat reasonable to argue that you can't generate random numbers, and that you just have a PRNG that has been seeded with your life's experiences. If you gave a TM extra input with that much entropy, then it would do a better job at picking secure keys than you would.

The one potential saving grace is something like the inherent randomness of quantum mechanics meaning that you really aren't a PRNG. Even then, you could say that the randomness isn't inherent in you and is just acting as an additional input, which would take us back to the first case.

I'm not sure how much credence I believe in these arguments. But you could, strictly speaking, say that your problem doesn't even fall within the purview of the Church-Turing hypothesis in the first place, because it's not a function. (Unless you look at it as a function of randomness, in which case we're back to the first case.)
EvanED
 
Posts: 4133
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI

Re: Possible counter-example to Church Turing Thesis

Postby troyp » Tue Apr 03, 2012 11:00 pm UTC

Goplat wrote:
WarDaft wrote:Not to mention that there's no evidence that the operations of neurons aren't computable by a Turing machine as well (by less in fact, but we don't need that for this particular case)
Actually, there is: Neuron-based life forms have been observed in rare cases to exhibit intelligence. (Since it appears you tend to hang out with Yudkowskybots, it's understandable you might not be aware of this.)

Since when is intelligence evidence of supra-turing computational abilities??
Not only is that speculative, it seems highly improbable (at least to me)

there is considerable reason to believe that any operation you can conceive of can be represented on a TM's tape
So "does this program halt or not" is inconceivable? I don't think that word means what you think it means.
and that it can do everything with that operation that you actually can.
OK, I'm not going to try to prove that I can solve the halting problem in the general case (even if I can, it would take infinitely long to demonstrate), so here's a different problem: let's see a Turing machine and input tape to generate secure 128-bit symmetric encryption keys, something I can do quite easily. (If it generates the same key every time, that's not secure).
I'd love to see that. I've never heard of a human generating randomness remotely as well as even the crappiest (artificial) PRNG, let alone better than any turing machine can.[/quote]
troyp
 
Posts: 529
Joined: Thu May 22, 2008 9:20 pm UTC
Location: Lismore, NSW

Re: Possible counter-example to Church Turing Thesis

Postby EvanED » Tue Apr 03, 2012 11:09 pm UTC

troyp wrote:I'd love to see that. I've never heard of a human generating randomness remotely as well as even the crappiest (artificial) PRNG, let alone better than any turing machine can.

Well, in Goplat's defense, if you're (unfairly, according to me) not allowing the TM to have a variable seed, then even the best PRNG is pretty bad. :-)
EvanED
 
Posts: 4133
Joined: Mon Aug 07, 2006 6:28 am UTC
Location: Madison, WI

Re: Possible counter-example to Church Turing Thesis

Postby WarDaft » Tue Apr 03, 2012 11:30 pm UTC

Goplat wrote:
WarDaft wrote:Not to mention that there's no evidence that the operations of neurons aren't computable by a Turing machine as well (by less in fact, but we don't need that for this particular case)
Actually, there is: Neuron-based life forms have been observed in rare cases to exhibit intelligence. (Since it appears you tend to hang out with Yudkowskybots, it's understandable you might not be aware of this.)
Wait, your saying it's impossible for a Turing Machine to model intelligence? No matter what? That's silly. It requires that the universe be fudamentally incomputable, not just non-deterministic (which can be trivially simulated by an NDTM, and thus by a DTM) which makes it a far more scary and confusing place than we would like to think. We don't have many ways of describing things where the rules that govern the syntactical correctness of our description are incomputable. And by not many, I mean zero. To find out that the universe fundamentally has no computable set of laws would be akin to finding out the moon is in fact made of cheese. And that it's angry cheese. No, actually, I think it would be worse.

And that's actually a pretty weird quip. Some of the things he says are pretty weird, and some are outright stupid, but he has some intelligent enough things to say too.

Goplat wrote:
WarDaft wrote:there is considerable reason to believe that any operation you can conceive of can be represented on a TM's tape
So "does this program halt or not" is inconceivable? I don't think that word means what you think it means.
I think it means exactly what I think it means. Many axiomatic mathematical systems are computable. Many of these systems can formulate the halting problem. Therefore, you can represent the question on a Turing Machine. You just can't answer it, in general, dependably, with one.
Goplat wrote:
WarDaft wrote:and that it can do everything with that operation that you actually can.
OK, I'm not going to try to prove that I can solve the halting problem in the general case (even if I can, it would take infinitely long to demonstrate), so here's a different problem: let's see a Turing machine and input tape to generate secure 128-bit symmetric encryption keys, something I can do quite easily. (If it generates the same key every time, that's not secure).
I'm not going to give you that, TMs are a real bother to program in. Instead, I'm going to put you in a plain white box, and take a perfect snapshot of it (pretend this doesn't violate QM for a moment) and then let you out and ask you for a key - you will be provided with a computer. Then, later I'm going to instantly fabricate a perfect copy of you from the snapshot, and ask you for the key again, in a manner fundamentally indistinguishable from the first time (again assume no interference from QM). You have 24 hours before I put you in the box to plan some mental tactic that will ensure that you give me two different keys. There will be no static from the environment, no random variations, you are the only possible source of two different keys. And I'm going to do the second one at a remote, undisclosed location, so that the 'first' you cannot interfere from the outside.


And actually, it is conceptually trivial to have a TM which produces a secure key. Give it a random oracle. (Or simulate an NDTM that returns all possible keys in a highly pseudo-random arrangement, and use the tape's initial state to select the branch you eventually return.) If certain QM results are truly as perfectly random as we suspect it to be, then it is in fact your random oracle, and the only reason you can possibly do these things you claim a TM cannot. Even if we don't go all the way down to QM, and call chaotic systems sufficiently random as a source... you are still using an external random oracle. Otherwise, you are only taking advantage of the fact that your brain itself represents a chaotic system on some levels, and contains a massive amount of entropy just due to its immense size (size from an information theoretic standpoint here.)
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
User avatar
WarDaft
 
Posts: 1574
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Possible counter-example to Church Turing Thesis

Postby troyp » Wed Apr 04, 2012 12:13 am UTC

EvanED wrote:
troyp wrote:I'd love to see that. I've never heard of a human generating randomness remotely as well as even the crappiest (artificial) PRNG, let alone better than any turing machine can.

Well, in Goplat's defense, if you're (unfairly, according to me) not allowing the TM to have a variable seed, then even the best PRNG is pretty bad. :-)

Well, I also think it's unfair to forbid the TM a variable key. After all, the human has plenty of sources of entropy to draw on.

Even without a variable key, though, the PRNG would still produce good numbers, in a sense. They'd just be no good for some purposes (such as cryptographic ones) since they could be predicted ahead of time and they'd be the same each time you ran the program. The same may well be true of the human if you could rerun it.

As you mentioned earlier, there's a chance that the human wouldn't choose deterministically, even if we could rerun it, if it's able to get entropy from quantum effects that is independent of both its state and input. *If* that's true, then the human does have *something* the TM doesn't, but as WarDaft said, all that thing would be is a random oracle (and not a very good one). We'd just need to augment the TM with a quantum "random" chip or something. I doubt our intelligence depends crucially on the ability to generate true randomness (particularly when we've consistently failed to demonstrate any such abililty).
troyp
 
Posts: 529
Joined: Thu May 22, 2008 9:20 pm UTC
Location: Lismore, NSW

Re: Possible counter-example to Church Turing Thesis

Postby Goplat » Wed Apr 04, 2012 2:26 am UTC

troyp wrote:Since when is intelligence evidence of supra-turing computational abilities??
Not only is that speculative, it seems highly improbable (at least to me)
One thing an intelligent being can do is solve arbitrary logic puzzles, like the ones posted three forums down from here. One type of logic puzzle is "does program X ever halt"; this always has a definite yes-or-no answer, but it has already been proven that no Turing machine is capable of correctly solving all of them.

Or take another thing considered to be characteristic of intelligence, use of natural language: no program so far has been capable of recognizing either spoken or written words with accuracy above even an unintelligent human (even recognition of printed words is often pretty poor). And attempts at programs that try to carry out conversation have thus far been utterly laughable.

WarDaft wrote:Wait, your saying it's impossible for a Turing Machine to model intelligence? No matter what?
Yes. It's true by definition under the strongest standard of intelligence, and empirically seems to be true under weaker definitions.
That's silly. It requires that the universe be fudamentally incomputable, not just non-deterministic (which can be trivially simulated by an NDTM, and thus by a DTM) which makes it a far more scary and confusing place than we would like to think. We don't have many ways of describing things where the rules that govern the syntactical correctness of our description are incomputable. And by not many, I mean zero.
But how many universes are there whose laws have been described completely and found to be computable? Even allowing hypothetical universes, as long as intelligence is proven possible in them, the answer is again zero. You can hardly say that an incomputable universe is unthinkable based on evidence, because there is none. And is it really any more scary and confusing than the idea that there exists a logic puzzle, with a definite yes-or-no answer, that you would never be able to solve even given unlimited time? Being inside a universe where everything is computable does imply that.

Regarding the randomness challenge: EvanED is right that it would be unfair to compare a system that includes a person delivering entropy to a key generator via the keyboard or whatever without taking into account that the person has "input" too. I was thinking of hardware RNGs using thermal noise, but it turns out that's actually not a standard feature on Intel chipsets as I thought it was (it's only on a few older ones). So, I may not personally have ready access to true randomness after all. Sorry.
Goplat
 
Posts: 490
Joined: Sun Mar 04, 2007 11:41 pm UTC

Re: Possible counter-example to Church Turing Thesis

Postby phlip » Wed Apr 04, 2012 3:33 am UTC

Goplat wrote:One thing an intelligent being can do is solve arbitrary logic puzzles, like the ones posted three forums down from here. One type of logic puzzle is "does program X ever halt"; this always has a definite yes-or-no answer, but it has already been proven that no Turing machine is capable of correctly solving all of them.

So, you know an intelligent being who is capable of determining whether a given TM halts, every time? Neat! Can you ask them what BB(5) is? Many people would love to know!

Goplat wrote:Or take another thing considered to be characteristic of intelligence, use of natural language: no program so far has been capable of recognizing either spoken or written words with accuracy above even an unintelligent human (even recognition of printed words is often pretty poor). And attempts at programs that try to carry out conversation have thus far been utterly laughable.

So, you have a proof that parsing natural language is incomputable? Not just not-yet-solved, but insolvable? Again, many people would love to see this proof! Do you intend to publish it at any point?
While no one overhear you quickly tell me not cow cow.
but how about watch phone?
User avatar
phlip
Restorer of Worlds
 
Posts: 7172
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia

Re: Possible counter-example to Church Turing Thesis

Postby WarDaft » Wed Apr 04, 2012 4:44 am UTC

Intelligence. You're really going to say that a TM cannot model intelligence. I'm not talking sentience here, just intelligence.

Well, I guess we better tell the entire machine learning community that they've been mass hallucinating these past... decades...

One thing an intelligent being can do is solve arbitrary logic puzzles, like the ones posted three forums down from here. One type of logic puzzle is "does program X ever halt"; this always has a definite yes-or-no answer, but it has already been proven that no Turing machine is capable of correctly solving all of them.
Then humans are not intelligent beings.

Pick any axiomatic system of math. There is a TM that cannot be proven to halt in it. We can build one explicitly (though it is a bit of work). There are many others, and we have no idea which ones they are. We cannot just invent more and more complicated systems, there is a maximum amount of information the brain can hold and usefully work with. If we fill that with our axioms (well first, we wouldn't have any room to remember the proof as we wrote it) we still have a finite size set of axioms, and so we (it might have to be a group effort) can construct a TM (it doesn't actually have to be a TM, any programming language in the world can be modeled by a TM so we can use something a lot higher level) which cannot be proven to halt or not in that system, which uses the maximum amount of information a human brain can hold.

Now do all that again, but with twice the amount of information in the axioms.

Thus, since we cannot solve arbitrary logic puzzles, human are not intelligent beings by your definition.

Note that computers have expandable memory, and so could easily work with an even more powerful axiomatic system to work on proving if the first one halts. The actual exercising of a proof isn't that difficult conceptually, it's really just a bunch of laws that transform finite sentences into other finite sentences, and the sentences you can actually reach in this way are the ones considered "true" in that system. Automated proofing systems have been made, the trick is making them efficient.

And is it really any more scary and confusing than the idea that there exists a logic puzzle, with a definite yes-or-no answer, that you would never be able to solve even given unlimited time?
Yes. Yes yes. Yes yes yes yes yes. If the laws of physics are incomputable, we will never learn them. They will require some operator whose actions we cannot describe without an infinite amount of information. One beautiful thing about QM is that it rejects the hidden variable hypothesis, otherwise, we would live in just such a world.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
User avatar
WarDaft
 
Posts: 1574
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Possible counter-example to Church Turing Thesis

Postby jareds » Wed Apr 04, 2012 10:50 am UTC

Goplat wrote:Yes. It's true by definition under the strongest standard of intelligence, and empirically seems to be true under weaker definitions.

What is the strongest standard of intelligence? Do you have any evidence that anything intelligent exists under this standard?
Alan Turing wrote:In other words then, if a machine is expected to be infallible, it cannot also be intelligent. There are several mathematical theorems which say almost exactly that. But these theorems say nothing about how much intelligence may be displayed if a machine makes no pretence at infallibility.

[Edit: I made the following more polite.]
The Lucas-Penrose argument requires very extreme beliefs about human abilities. It doesn't necessarily require personal arrogance, but it does require arrogance about the abilities of humanity as a whole. (Penrose more or less argues that the human mathematical community could be infallible if it were really careful.) This is not to say that the belief that humans aren't TMs is inherently nuts, but the argument in question is really dubious. Yes, Penrose is probably smarter than me, but that doesn't mean he can't make a nutty argument. I'm sure that there are people smarter than me who would argue that the Bible is inerrant because the Bible says that the Bible is inerrant.

Arguing that humans are clearly more intelligent than TMs because humans can clearly determine whether any TM halts is a bit like arguing that humans are clearly more intelligent than any other life in the galaxy more than one million years old because nothing has yet colonized the entire galaxy but humans clearly will have colonized the entire galaxy in one million years.

I'm sorry if you personally find it scary that humans have intellectual limitations, but fear is not evidence, and the claim that humanity is a halting oracle requires extraordinary evidence.

Arguing that humans are more intelligent than TMs because humans can't make computers solve halting problems nearly as well as humans is neither better nor worse than observing that humans can't make computers write novels nearly as well as humans. Neither direction is totally crazy, although as you might expect I think this is mostly evidence about human ability to make computers do things.

Sure, we indeed don't know the complete laws of physics. But all the ones we know are computable, and we know the ones that would plausibly matter for brains pretty well. Certainly I've never heard of any empirical evidence for brains being inexplicable by chemistry, as opposed to philosphical objections to it.
jareds
 
Posts: 408
Joined: Wed Jan 03, 2007 3:56 pm UTC

Re: Possible counter-example to Church Turing Thesis

Postby Yakk » Wed Apr 04, 2012 1:22 pm UTC

phlip wrote:
Goplat wrote:One thing an intelligent being can do is solve arbitrary logic puzzles, like the ones posted three forums down from here. One type of logic puzzle is "does program X ever halt"; this always has a definite yes-or-no answer, but it has already been proven that no Turing machine is capable of correctly solving all of them.

So, you know an intelligent being who is capable of determining whether a given TM halts, every time? Neat! Can you ask them what BB(5) is? Many people would love to know!

For those who do not know BB(5) is the Max number of steps that a TM with only five states and an empty initial tape can run before halting. (Or was it how much it writes? No matter, they are as hard to calculate). These are teeny tiny TMs but human beings are unable to solve the halting problem on them. Claims that humans can solve the halting problem on arbitrary TMs is laughable in this light.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10427
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Possible counter-example to Church Turing Thesis

Postby troyp » Wed Apr 04, 2012 4:44 pm UTC

jareds wrote:The Lucas-Penrose argument requires very extreme beliefs about human abilities. It doesn't necessarily require personal arrogance, but it does require arrogance about the abilities of humanity as a whole. (Penrose more or less argues that the human mathematical community could be infallible if it were really careful.) This is not to say that the belief that humans aren't TMs is inherently nuts, but the argument in question is really dubious. Yes, Penrose is probably smarter than me, but that doesn't mean he can't make a nutty argument. I'm sure that there are people smarter than me who would argue that the Bible is inerrant because the Bible says that the Bible is inerrant.

Yeah, no amount of intelligence precludes irrational beliefs. It can help protect against them, but it's not a panacea, especially when the victim is willing...
It's been ages since I read Penrose's arguments about intelligence, and I'm not really qualified to weigh them up, but I remember having the distinct impression that he was trying to rationalize something he wanted to believe, rather than explaining a belief that derived from rational thought.

The problem with smart people is, if they want to, they can usually come up with good enough rationalizations to fool themselves.
troyp
 
Posts: 529
Joined: Thu May 22, 2008 9:20 pm UTC
Location: Lismore, NSW

Re: Possible counter-example to Church Turing Thesis

Postby HungryHobo » Mon Apr 16, 2012 10:21 am UTC

Yakk wrote: Claims that humans can solve the halting problem on arbitrary TMs is laughable in this light.



people assume that since they can debug a program pretty well and can normally figure out if a normal little program halts then they're doing something a TM can't.

A TM is theoretically perfectly capable of giving just as good an answer to the halting problem as a human as long as it's allowed to be wrong sometimes or answer with "maybe" sometimes just like humans.

I blame how poorly the halting problem is taught in colleges, even in good theory of computation classes.

For one there's never been a computer built in the physical universe to which the halting problem actually applies.

A theoretical deterministic turing machine with an infinite tape can solve the halting problem for any finite turing machine or finite state machine(like any computer in existance) in finite time.
Give a man a fish, he owes you one fish. Teach a man to fish, you give up your monopoly on fisheries.
HungryHobo
 
Posts: 1436
Joined: Wed Oct 20, 2010 9:01 am UTC

Re: Possible counter-example to Church Turing Thesis

Postby Robert'); DROP TABLE *; » Mon Apr 16, 2012 5:41 pm UTC

HungryHobo wrote:For one there's never been a computer built in the physical universe to which the halting problem actually applies.

AFAIK, the halting problem applies to all computers in aggregate, rather than individual instances. However, there's also the fact that nobody's been able to tell what circumstances, if any, lead to the brain "halting," other than hardware failure.
...And that is how we know the Earth to be banana-shaped.
User avatar
Robert'); DROP TABLE *;
 
Posts: 684
Joined: Mon Sep 08, 2008 6:46 pm UTC
Location: in ur fieldz

Re: Possible counter-example to Church Turing Thesis

Postby korona » Mon Apr 16, 2012 6:11 pm UTC

If a human can determine whether a given turing machine/computer program halts and he/she can explain the reason to another human then this explanation can be converted to a proof in your favorite theory (ZF for example) that the turing machine halts. If there is a proof in such a theory it can be found by an automated theorem prover, so a turing machine can also determine whether the initial program halts.
This procedure only fails if the human is unable to explain why the program halts or if the explanation cannot be converted to a proof in a suitable proof system because it uses non-standard and/or infinite first-order axioms.
korona
 
Posts: 351
Joined: Sun Jul 04, 2010 8:40 pm UTC

Re: Possible counter-example to Church Turing Thesis

Postby jareds » Tue Apr 17, 2012 5:14 am UTC

korona wrote:If a human can determine whether a given turing machine/computer program halts and he/she can explain the reason to another human then this explanation can be converted to a proof in your favorite theory (ZF for example) that the turing machine halts. If there is a proof in such a theory it can be found by an automated theorem prover, so a turing machine can also determine whether the initial program halts.
This procedure only fails if the human is unable to explain why the program halts or if the explanation cannot be converted to a proof in a suitable proof system because it uses non-standard and/or infinite first-order axioms.

This is kind of unfair. The non-computable-human camp aren't outright illogical. I'm sure they understand that halting-oracle humanity can't be limited to proofs in a fixed formal system--that's almost exactly their point! The obvious counterargument is:
(1) Humans don't "explain" by giving each other formal proofs. Nor is the human mathematical community working within a fixed formal system, for all practical purposes (e.g., if one dubs some sort of simulation of the universe as a formal system, that provides no practical way of communicating proofs). If you had asked mathematicians at the turn of the 20th century to settle on a formal system for all time (and by some miracle they did), I'm sure they would have settled on something that does not prove things that are now accepted, and I'm sure the same the same problem would occur at any point in time. Humans are free to convince each other to accept new axioms or formal systems by metamathematical argument, and they do so in practice.
(2) Humanity would, in principle, given time, accept an infinite family of axioms and/or formal systems sufficient to prove or disprove the halting of any TM, without accepting any that were not true/sound (or at least 1-consistent).

The ridiculous part is (2). (1) is totally reasonable. [Edit: Of course, for (2) to be possible, you have to remove the "for all practical purposes" disclaimer from (1).]

While I don't agree at all with (2), I think the non-computable-human camp would generally not hesitate to agree with (2), or something similar, which makes your argument a strawman. I don't think anyone says that humans can solve the halting problem within a fixed formal system.
jareds
 
Posts: 408
Joined: Wed Jan 03, 2007 3:56 pm UTC

Re: Possible counter-example to Church Turing Thesis

Postby WarDaft » Tue Apr 17, 2012 7:16 pm UTC

Actually, if allowed to run forever, (2)'s vaguely reasonable (aside from a finite observable universe), and even can even be represented by a Turing machine. There is no TM that a TM cannot eventually have correct 'belief' about the halting of, it's just that it can never actually do so and then halt.

Consider a TM that runs all TMs in a dovetailing fashion, which assumes that every TM does not halt until it finds that it halts, and uses these assumptions to run an oracle TM. Eventually, if the OTM does indeed halt, all of the TMs it relies on to be computed will have either been detected to halt by the first TM, or are correctly assumed to not halt, so eventually the TM will 'settle' on a value. But there's no possible way it can do this and then decide to halt and be assuredly correct.

And that's rather how the human study of mathematics has been going. We go with something, possibly find a problem, and then go with something slightly different; always assuming what we have at the moment is right.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
User avatar
WarDaft
 
Posts: 1574
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Possible counter-example to Church Turing Thesis

Postby jareds » Tue Apr 17, 2012 9:43 pm UTC

There may be some confusion about what I meant. I did not mean anything hazy about what would happen "at infinity". Perhaps I should have said "unbounded" rather than infinite. I meant:
(2) At any finite time, humanity will accept some finite set of axioms and formal systems. For every TM, there exists a finite time at which humanity can prove it halts or does not halt from the axioms and formal systems that it accepts. At no finite time does humanity accept anything 1-inconsistent*. [edit: the systems include at least Peano arithmetic at all time] It is an obvious logical necessity that the set of all axioms and formal systems that humanity will ever accept is infinite.

I think my statement is a reasonable reflection of what people believe when they believe the the human mind is non-computable for such reasons. Plainly, this makes humanity a halting oracle.

In your scenario, there is no finite time at which anything is proven not to halt.

*I assume that anyone holding such a belief would make "humanity accepts" really strict so that we have never yet accepted anything 1-inconsistent. Since I don't agree with the statement, this isn't really my problem.
Last edited by jareds on Tue Apr 17, 2012 10:53 pm UTC, edited 2 times in total.
jareds
 
Posts: 408
Joined: Wed Jan 03, 2007 3:56 pm UTC

Re: Possible counter-example to Church Turing Thesis

Postby WarDaft » Tue Apr 17, 2012 10:06 pm UTC

The assumptions the TM makes about halting are essentially axioms, and define what it can see to be true if it included an actual proof writing aspect. It just overturns them more than we do. Well maybe, we might do a lot of throwing out of axioms in the limit.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
User avatar
WarDaft
 
Posts: 1574
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Possible counter-example to Church Turing Thesis

Postby jareds » Tue Apr 17, 2012 10:58 pm UTC

WarDaft wrote:The assumptions the TM makes about halting are essentially axioms, and define what it can see to be true if it included an actual proof writing aspect. It just overturns them more than we do. Well maybe, we might do a lot of throwing out of axioms in the limit.

OK...I was implicitly assuming that humanity's accepted formal systems include Peano arithmetic at all times. With this assumption, your axioms will be inconsistent at every finite time, which I expressly rejected in (2). Obviously, if you don't include any arithmetic, no incompleteness results apply: you can potentially just have an formal system that says that no TM halts, for example.
jareds
 
Posts: 408
Joined: Wed Jan 03, 2007 3:56 pm UTC

Re: Possible counter-example to Church Turing Thesis

Postby WarDaft » Tue Apr 17, 2012 11:17 pm UTC

The TM is just more obviously naive than we are. We don't know that PA is consistent, the TM is just doing less work to detect inconsistent axioms and considering more at any particular time.

I'm not saying people are incomputable, just that we don't exactly see our progress as ending, and so are naturally equivalent to a TM that doesn't halt but incrementally updates its own 'beliefs'. Those beliefs aren't exactly what I put forward, because I was just going for a simple example. If we put a hard end to the human race, well, as a species we've halted, and are obviously equivalent to a halting TM.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
User avatar
WarDaft
 
Posts: 1574
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Possible counter-example to Church Turing Thesis

Postby troyp » Tue Apr 17, 2012 11:46 pm UTC

jareds wrote:This is kind of unfair. The non-computable-human camp aren't outright illogical.

The more sophisticated ones, anyway*. But this isn't saying much: we're talking about an empirical proposition, so of course it's possible to make logically consistent arguments to support it. And given how much we don't know about the universe and the human mind, you can even make an argument that can't actually be empirically refuted. I'd be more interested in a justification of why anyone would believe humans are capable of supraturing computation, given what we do know.
jareds wrote: I'm sure they understand that halting-oracle humanity can't be limited to proofs in a fixed formal system--that's almost exactly their point!

Yeah, I agree it's pointless to make arguments based on humans working in a fixed formal system. Humans don't perform all their cognition *explicitly* within any such system, we reason intuitively. So this pushes the issue down to the level of our brain (or - by inclusion - the universe in general). Can we regard our cognitive processes (or possibly even the whole universe) as being equivalent (at least in practice) to a turing machine?

* Actually, didn't some of the most famous ones claim basically "Godel's theorem shows a computer can never prove certain propositions, but I know they're true so I'm inherently superior to any machine". In fact, didn't *Penrose* pretty much say that (and then say "it's the magic quantum neurons that do it")? Or am I misremembering? Because that argument is pretty illogical.
troyp
 
Posts: 529
Joined: Thu May 22, 2008 9:20 pm UTC
Location: Lismore, NSW

Re: Possible counter-example to Church Turing Thesis

Postby jareds » Wed Apr 18, 2012 12:45 am UTC

WarDaft wrote:The TM is just more obviously naive than we are. We don't know that PA is consistent, the TM is just doing less work to detect inconsistent axioms and considering more at any particular time.

You are the one who said that my original (2), which stated that humanity would not "accept[] any [axioms and/or formal systems] that were not true/sound (or at least 1-consistent)", was "vaguely reasonable".

(2) was an attempt to state the heart of the ridiculous implication of the argument that humans are non-computable because of the halting problem and/or incompleteness theorem. If you're saying that humanity is not infallible at weeding out inconsistent theories, then of course I agree, but that's a serious problem for (2).

troyp wrote:The more sophisticated ones, anyway*. But this isn't saying much: we're talking about an empirical proposition, so of course it's possible to make logically consistent arguments to support it.

Yeah, I agree with everything you said. I was only talking about logical coherence. It is logically coherent for Penrose to claim that he's an oracle that can see the consistency of a formal system and therefore know that its Gödel sentence is true, but, going back to my original post in this thread, it requires a certain amount of arrogance.
jareds
 
Posts: 408
Joined: Wed Jan 03, 2007 3:56 pm UTC

Re: Possible counter-example to Church Turing Thesis

Postby WarDaft » Wed Apr 18, 2012 2:40 pm UTC

You are the one who said that my original (2), which stated that humanity would not "accept[] any [axioms and/or formal systems] that were not true/sound (or at least 1-consistent)", was "vaguely reasonable".

(2) was an attempt to state the heart of the ridiculous implication of the argument that humans are non-computable because of the halting problem and/or incompleteness theorem. If you're saying that humanity is not infallible at weeding out inconsistent theories, then of course I agree, but that's a serious problem for (2).
I'm saying we're not infallible at it, but no one actually expects (for example) PA to have any contradictions show up, even though it's still entirely possible for it to happen at almost any point. There are lots of theorems we accept as "true" because they've been proven in PA. We don't absolutely know the rules we have work, but we can iteratively (and up to the thermodynamic limit, indefinitely) discard ones that we find don't work. So eventually we will have correct but not fully justified beliefs about the halting of various machines, because we've 'proven' them. We don't know when we actually have them, we just tend to assume the current proofs we have are in consistent systems.

That is, we can eventually accept an unbounded set of axioms, and believe them all to be true, and not accept any contradictory axioms for an infinitely long time (where as non-contradictory axioms we can accept indefinitely).

The point I was making was that the TM I described does the same thing, though much more simplistically and naively, and will eventually come to have correct beliefs about many OTMs... so it's not unreasonable to allow the same of humanity. It's still computable operations more or less.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
User avatar
WarDaft
 
Posts: 1574
Joined: Thu Jul 30, 2009 3:16 pm UTC


Return to Computer Science

Who is online

Users browsing this forum: No registered users and 1 guest