1
$\begingroup$

I recognize that it has overwhelming consensus at this point, but from what I understand, it's still technically considered "probably true" instead of "definitely true".

If we go by their original definition, then it amounts to dealing with things that can be accomplished by "effective methods", meaning finite sets of instructions of specific steps that can be carried out (when applicable) in finite time. Basically, it sounds logically identical to our modern conception of an algorithm.

If that were the case, then by simply having a computer (with infinite memory, of course) enumerate every possible program and execute them in dovetail-succession so that all halting programs will eventually halt, you would be guaranteed to hit upon any more-powerful computational technique which could be carried out with an "effective method" sooner or later. However, this is clearly impossible since by definition any such method could not be carried out by a computer (or Turing machine, or whatever).

I am certain I am retreading old ground here but could not find it on search. Do I have the thrust of their thesis wrong, or is there a flaw in my find-it-with-enumeration approach?

I also realize that I have possibly oversimplified their thesis to "anything a computer can do, a computer can do", but I'm finding a hard time getting around that.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Because what can be effectively carried out depends on what is possible within the physics of our universe. So if we have not correctly understood physics, it is possible that perhaps more might be possible than we can currently imagine. While that doesn't seem likely, it's not something we can absolutely definitively rule out, so there is no basis for treating the Church-Turing hypothesis as definitely proven.

Or, to put it another way, there is no proof of the Church-Turing hypothesis, so therefore there is no basis to consider it proven. In fact, there is not even an accepted precise, rigorous formulation of exactly what the CT is claiming.

See, e.g., the extended Church-Turing hypothesis, which might sound roughly as plausible as the Church-Turing hypothesis, which your line of argumentation seems just as valid for as for the normal Church-Turing hypothesis, and yet for which we have valid reasons to believe is false, given what it appears quantum computers can achieve.

As another example, if time travel is possible (specifically, closed timelike travel), then the computational power achievable is far greater than what our current computers can achieve. See https://cstheory.stackexchange.com/q/43920/5038.

Related reading:

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.