We will then prove in a later post that conditions 2.5 or 2.6 will lead to a larger set of computable functions than a UTM can compute, and thus the Church-Turing Thesis is false, in that it’s not universally valid, that is it doesn’t hold in every model. It is satisfiable, however, in that there exists a model where it’s correct.
I think you are overclaiming here. I’m not a philosopher of computation, but it seems fair to say that the Church-Turing thesis refers to the specific model gestured at by the simplified model of reality where you allow unbounded space and time usage, and no edge cases of physics or quantum phenomena etc. Similarly, the natural numbers as such don’t depend on any mathematical model, but they are what you get if you “just keep counting”.
There’s a new version of it here that I post for completeness, but I’ll respond to the old one below:
We will then prove in a later post that conditions 2.5 or 2.6 will lead to a larger set of computable functions than a UTM can compute, and thus the Church-Turing Thesis is false. However, by dropping both conditions, and by adding a new condition by hand that restricts what we can do with effective functions, it can be true.
New quote:
I’m not a philosopher of computation, but it seems fair to say that the Church-Turing thesis refers to the specific model gestured at by the simplified model of reality where you allow unbounded space and time usage, and no edge cases of physics or quantum phenomena etc.
The problem is that given the assumption and my conditions, it is easy to show that under condition 2.6 that I can make a larger set of functions that are computable by a human in a simulated UTM universe than the original UTM could compute, and that there must exist a computation that a human with unlimited time and memory does that the UTM simulates that is not computable according to the original definition.
The process is best explained by the website below, but it basically uses a trick where an uncountable infinity of branches can be generated by only a countable infinity of vertices and edges (The Turing Machines.)
The problem is that unbounded time and memory starts to let you simulate things that you should have no business simulating, so if you want to avoid the consequences, you either need to constrain the Universal Turing Machine’s time or memory, or put in a condition by hand stating that you can’t simulate non-computable functions.
Another problem is that this is not reasonable to ask for when defending a universal claim:
and no edge cases of physics or quantum phenomena etc.
That’s the problem, because the edge cases matter for a universal claim, like what I suspect Church and Turing were doing, as it points to why the thesis doesn’t work. As an existential claim, it would work, but as a universal claim it fails.
I think you are overclaiming here. I’m not a philosopher of computation, but it seems fair to say that the Church-Turing thesis refers to the specific model gestured at by the simplified model of reality where you allow unbounded space and time usage, and no edge cases of physics or quantum phenomena etc. Similarly, the natural numbers as such don’t depend on any mathematical model, but they are what you get if you “just keep counting”.
There’s a new version of it here that I post for completeness, but I’ll respond to the old one below:
New quote:
The problem is that given the assumption and my conditions, it is easy to show that under condition 2.6 that I can make a larger set of functions that are computable by a human in a simulated UTM universe than the original UTM could compute, and that there must exist a computation that a human with unlimited time and memory does that the UTM simulates that is not computable according to the original definition.
The process is best explained by the website below, but it basically uses a trick where an uncountable infinity of branches can be generated by only a countable infinity of vertices and edges (The Turing Machines.)
http://www.amirrorclear.net/academic/ideas/simulation/index.html
The problem is that unbounded time and memory starts to let you simulate things that you should have no business simulating, so if you want to avoid the consequences, you either need to constrain the Universal Turing Machine’s time or memory, or put in a condition by hand stating that you can’t simulate non-computable functions.
Another problem is that this is not reasonable to ask for when defending a universal claim:
That’s the problem, because the edge cases matter for a universal claim, like what I suspect Church and Turing were doing, as it points to why the thesis doesn’t work. As an existential claim, it would work, but as a universal claim it fails.