I didn’t check the article yet but if I understood your comment correctly then a simpler example would have been “turing machines with a halting oracle”, which is indeed stronger than normal turing machines.
(Per my understanding) the church-turing thesis is about having a good formal definition of “the” intuitive notion of algorithm. And an important property of this intuitive notion is that a “perfectly rigorous idiot” could run any algorithm with just paper and a pen. So I would say it is wrong to take something that goes beyond that as a counterexample.
Maybe we should clarify this concept of “the intuitive notion of algorithm”.
PS: We are running dangerously close to just arguing semantics, but insofar as “the church-turing thesis” is a generally consensual notion I do not think the debate is entirely pointless.
I do think this is possibly going to degenerate into a word game, but the thing I remember from the wikipedia is that all algorithms that a human can effectively calculate with pen and paper are the computable functions, and the problem here is either the human has real limitations on time like real humans, and thus the set of computable functions is much smaller than all total computable functions, or we don’t, and the problem here is CTC computers that solve the halting problem can be simulated by a Universal Turing Machine, thus CTC spacetimes will eventually be learned by a human with unlimited time and memory, and at that point the set of computable functions is larger than the original definition, causing a contradicton.
To ensure that this is valid, we will be relying on a construction like this, which tells us that while Universal Turing Machines can’t compute the halting function, it can simulate the halting function anyway, so long as the infinite bitstring that computes the halt function for Turing Machines is simulated with every other bitstring, we can emulate a computer that knows the halt function, and thus a human must be able with unlimited time and memory to compute more things than a Turing Machine.
Here’s the link below on the details of this process:
Thus, the set of computable functions must be larger or smaller than defined, contradicting the Church Turing Thesis as written.
It’s okay to say that your intuitive notion of computability is exactly equivalent to the Universal Turing Machine, but then say that instead of insisting that every notion of computability is the same thing.
Ok, I think I can clarify what people generally mean when they consider that the logic Church-Turing thesis is correct.
There is an intuitive notion of computation that is somewhat consensual. It doesn’t account for limits on time (beyond the fact that everything must be finitely long) and does not account for limits in space / memory.
It is also somewhat equivalent to “what a rigorous idiot could be made to do, given immortality and infinite paper/pen”.
Many people / most computer scientist share this intuitive idea and at some point people thought they should make more rigorous what it is exactly.
Whenever people tried to come up with formal processes that only allow “obviously acceptable” operations with regard to this intuitive notion, they produced frameworks that are either weaker or equivalent to the turing machine.
The Church-Turing thesis is that the turing machine formalism fully captures this intuitive notion of computation. It seems to be true.
With time, the word “computable” itself has come to be defined on the basis of this idea. So when we read or hear the word in a theoretical computer-science context, it now refers to the turing machine.
Beyond this, it is indeed the case that the word “computation” has also come to be applied to other formalisms that look like the initial notion to some degree. In general with an adjective in front to distinguish them from just “computation”. We can think for example of “quantum computing”, which does not match the initial intuition for “computation” (though it is not necessarily stronger). These other applications of the word “computation” are not what the Church-Turing thesis is about, so they are not counterexamples.
Also, all of this is for the “logic” Church-Turing thesis, to which what can be built in real life is irrelevant.
PS: I take it for granted that computer scientists, including those knowledgeable on the notions at hand, usually consider the thesis correct. That’s my experience, but maybe you disagree.
I didn’t check the article yet but if I understood your comment correctly then a simpler example would have been “turing machines with a halting oracle”, which is indeed stronger than normal turing machines. (Per my understanding) the church-turing thesis is about having a good formal definition of “the” intuitive notion of algorithm. And an important property of this intuitive notion is that a “perfectly rigorous idiot” could run any algorithm with just paper and a pen. So I would say it is wrong to take something that goes beyond that as a counterexample.
Maybe we should clarify this concept of “the intuitive notion of algorithm”.
PS: We are running dangerously close to just arguing semantics, but insofar as “the church-turing thesis” is a generally consensual notion I do not think the debate is entirely pointless.
I do think this is possibly going to degenerate into a word game, but the thing I remember from the wikipedia is that all algorithms that a human can effectively calculate with pen and paper are the computable functions, and the problem here is either the human has real limitations on time like real humans, and thus the set of computable functions is much smaller than all total computable functions, or we don’t, and the problem here is CTC computers that solve the halting problem can be simulated by a Universal Turing Machine, thus CTC spacetimes will eventually be learned by a human with unlimited time and memory, and at that point the set of computable functions is larger than the original definition, causing a contradicton.
To ensure that this is valid, we will be relying on a construction like this, which tells us that while Universal Turing Machines can’t compute the halting function, it can simulate the halting function anyway, so long as the infinite bitstring that computes the halt function for Turing Machines is simulated with every other bitstring, we can emulate a computer that knows the halt function, and thus a human must be able with unlimited time and memory to compute more things than a Turing Machine.
Here’s the link below on the details of this process:
https://www.amirrorclear.net/academic/ideas/simulation/index.html
Thus, the set of computable functions must be larger or smaller than defined, contradicting the Church Turing Thesis as written.
It’s okay to say that your intuitive notion of computability is exactly equivalent to the Universal Turing Machine, but then say that instead of insisting that every notion of computability is the same thing.
Ok, I think I can clarify what people generally mean when they consider that the logic Church-Turing thesis is correct.
There is an intuitive notion of computation that is somewhat consensual. It doesn’t account for limits on time (beyond the fact that everything must be finitely long) and does not account for limits in space / memory. It is also somewhat equivalent to “what a rigorous idiot could be made to do, given immortality and infinite paper/pen”. Many people / most computer scientist share this intuitive idea and at some point people thought they should make more rigorous what it is exactly.
Whenever people tried to come up with formal processes that only allow “obviously acceptable” operations with regard to this intuitive notion, they produced frameworks that are either weaker or equivalent to the turing machine.
The Church-Turing thesis is that the turing machine formalism fully captures this intuitive notion of computation. It seems to be true.
With time, the word “computable” itself has come to be defined on the basis of this idea. So when we read or hear the word in a theoretical computer-science context, it now refers to the turing machine.
Beyond this, it is indeed the case that the word “computation” has also come to be applied to other formalisms that look like the initial notion to some degree. In general with an adjective in front to distinguish them from just “computation”. We can think for example of “quantum computing”, which does not match the initial intuition for “computation” (though it is not necessarily stronger). These other applications of the word “computation” are not what the Church-Turing thesis is about, so they are not counterexamples. Also, all of this is for the “logic” Church-Turing thesis, to which what can be built in real life is irrelevant.
PS: I take it for granted that computer scientists, including those knowledgeable on the notions at hand, usually consider the thesis correct. That’s my experience, but maybe you disagree.