[Question] What is the evidence on the Church-Turing Thesis?

Why do you believe that everything “effectively computable” can be computed by a Turing machine? In the same vein: How would you recognize this to be false?

I don’t particularly doubt that this is true. But I want to get a better gears level understanding for why this might be true. When this came up during my “fundamentals of computer science” class, my professor was communicating high confidence that this was essentially correct (joking he could speed up the graduation of the student who would show this is false), but gave very little info on why he believed this in the first place.

I got a bit more out of the respective Wikipedia article. I get that people have come up with different formalisms for “effectively computable” and they all seem to be weaker or equivalent to Turing machines, and that does seem like compelling evidence. But, I want to understand whether there is more to it. There seem to be points in favor, like this quote from Gödel that I pulled from the Wikipedia article:

It may also be shown that a function which is computable [‘reckonable’] in one of the systems Si, or even in a system of transfinite type, is already computable [reckonable] in S1. Thus the concept ‘computable’ [‘reckonable’] is in a certain definite sense ‘absolute’, while practically all other familiar metamathematical concepts (e.g. provable, definable, etc.) depend quite essentially on the system to which they are defined …

Does this mean: The act of showing that something would be computable in a System would effectively show how to do it with a System (e. g. a Turing machine?). To me this seems kind of circular and to rely on the fact that there is no “stronger” formal system that would itself be stronger as a Turing machine that we would use to show the existence of such a system (this is probably a confused thought, so help in understanding this would be welcome)?

Another thought: What if our brains just happen to be Turing machines (but other things in the world are “stronger”) and there is just no way to formally describe these higher level Algorithms with our limited brains (analogy: Could our brains come up with Turing machines if they were finite automatons?). Could there be ways for us to notice if this was the case?

So to sum up, I still find this quite confusing and thought this might be the right place to get good answers or to clarify these points.

No comments.