As an undergraduate with limited understanding of QC and even the C-T thesis, I have problems figuring out why in questions such as Extended Church-Turing Thesis real-life quantum stuff is even given the time of day, because it's not relevant is it?
I have always thought of the C-T thesis as a statement, specifically a statement in theoretical computer science. A statement that reads, "There exists no computation model capable of recognising languages that a Turing Machine cannot". Even that is a bit messy for me. Is there a formal definition for a computation model? Finite alphabet, finite states, what exactly are we talking about here?
Whether provable or not is another story, but it's a statement that evaluates to some logical value or another. Some people say that the C-T is a statement, some actually say it's not. I have no authority in this, so I'm left as confused as ever.
And if it's not a statement, then great! It's not a problem anymore. At least from the mathematical side of things.
I have a couple of what I think are misconceptions. I've taken a look at the
Chomsky Hierarchy of grammars, and at the very top lie all the so called
Unrestricted Grammars which have been proven to be equally expressive as Turing Machines, apparently. Now I don't even know the formal definition for expressivity, all I have is an intuitive understanding. CFGs are more "expressive" than DFAs and CSGs are more "expressive" than CFGs etc etc, because they can recognise all the languages the prior construction can and more. Is this actually the commonly accepted definition?
Now Unrestricted Grammars specifically, allow production rules of the form $\alpha \to \beta$ where $\alpha$ is any non-empty string and $\beta$ is any string. Hence, unrestricted. How on earth could a computational model compete with something that is literally unrestricted? It makes me think of the C-T thesis as trivial, "of course" it's true.
This left me even more confused: What would it mean to disprove Church-Turing thesis?
The accepted answer to this question starts off with:
The Church-Turing thesis has been proved for all practical purposes.
Why is practicality suddenly worth anything in theoretical computer science?
Are there like two interpretations or more of the C-T thesis, one for "practical purposes" and one for "mathematics"?