Why you can't treat decidability and complexity as a constant (Post #1)
8interstice
-1Noosphere89
6Algon
0Noosphere89
5Algon
8Noosphere89
5Noosphere89
5Amarko
2Noosphere89
3Amalthea
2Noosphere89
3Amarko
3Noosphere89
New Comment
caused a lot of problems for Church and Turing et al in that they incorrectly jumped to the conclusion that the Turing Machines could compute any possible computer, or compute any possible algorithm
The Church-Turing thesis is about what things can be effectively computed in reality. Obviously you can define hypothetical machines that exceed the Turing machine, and this was already known to Church and Turing. CTC computers that can solve the halting problem don't disprove the CTT unless they can actually be built.
1Note that the original thesis made no reference to our specific reality at all, as it was instead defined on effective functions.
Thus I can use essentially arbitrary changes to the model, and I can still break the thesis if there's any extension of a Turing Machine that let's you compute more things.
Right now, I'm only trying to determine possibility, in a philosophical sense, not something that I know could be done.
If I recall correctly, "effective" is referring to a method which can exist in our reality. I'd be suprised if you could find a quote from the original papers suggesting otherwise.
1I went to the wikipedia page, and the notion of effective functions was defined like this:
It consists of a finite number of exact, finite instructions. When it is applied to a problem from its class: It always finishes (terminates) after a finite number of steps. It always produces a correct answer. In principle, it can be done by a human without any aids except writing materials. Its instructions need only to be followed rigorously to succeed. In other words, it requires no ingenuity to succeed.[4]
Critically, nothing about the specific constraints of reality were ever stated in the problem. Also, the human.
Here's the article where I got it from.
Before I reply to this, I'd like to note that if your point is that the limits of effective functions depend on what kind of universe the functions are executed in, then I claimn that people on LW accept that thesis already. But we don't accept that the extended church-turing is wrong. A plurality of LW users would say It is probably right. And what we mean by that is that any process we care about in our world can be simulated accurately enough for our purposes by a recursively computable function.
As far as I can tell, this is the what most people mean by the extended-church-turing thesis. Heck, that's what Turing meant by it. Or, at least, he didn't mean what I think you claim he meant. He was the first to investigate machines which could compute the undecidable. He calld them O-machines in his thesis. And if Wikipedia gives a different definition, then so much the worse for Wikipedia!
I don't think we actually disagree here about the limits of computation. I think we agree that what we can only compute recursive functions in our universe, and that in other universes this could easily be different. Rather, we just over what things like "effective functions" mean, or what chuch-turing means etc. And I suspect that's why other people were downvoting your post. They probably read your psot and thought you didn't understand basic computability theory. But to me, it looks like you do understand computability theory but are simply using some terms incorrectly. The disagreement is purely semantic.
If you re-wrote your post in light of this, I suspect it would fair much better here.
I don't think we actually disagree here about the limits of computation. I think we agree that what we can only compute recursive functions in our universe, and that in other universes this could easily be different. Rather, we just over what things like "effective functions" mean, or what chuch-turing means etc. And I suspect that's why other people were downvoting your post. They probably read your psot and thought you didn't understand basic computability theory. But to me, it looks like you do understand computability theory but are simply using some terms incorrectly. The disagreement is purely semantic.
That was definitely most of the disagreement, as I remembered a different version of the Church-Turing Thesis than some other people had, and I definitely had different ideas of what effective functions meant to people (I didn't anticipate people assuming constraints that weren't in the problem on Wikipedia.)
My fundamental claim is that the Church-Turing Thesis is not valid, to use terms for logic, that is it doesn't hold for every model.
I'd probably have a post on what we can actually compute later on, but I mostly agree that with some caveats, as is anything pertaining to the long-term future, the set of functions we can compute is smaller than the set of computable functions as traditionally defined.
But yes, I will rewrite this post, mostly to make it clear what I'm arguing against.
Or, at least, he didn't mean what I think you claim he meant.
What he didn't realize, apparently, is that this makes the claim, as I stated it, essentially invalid, but it's still satisfiable, since there exist models where the Church-Turing Thesis is true. I think the biggest disagreement was whether the Church-Turing Thesis was an existential claim about computers, or a universal claim about computers, and also a disagreement about which constraints are assumed into the problem, but also an imprecision over which models are allowed or reasonable.
And the extended version again has a problem with the use of the word "reasonable" in it's definition, and IMO this is a pretty big problem, when people use the word reasonable to motte-and-bailey criticisms of the thesis.
Nevertheless, I will rewrite this post, and thanks for commenting.
I made a major rewrite of this post, in that I defined what Church and Turing were likely talking about, and importantly defined what the effective methods could do and what constraints were placed on them, or alternatively what the algorithm must do, and what constraints on the algorithms must follow.
Critically, while algorithm running times and memory/space are always finite, they are not bounded in the time or memory/space.
Also, it is universally quantified, as it includes something close to a for-all condition, rather than existentially quantified.
It seems to me that the constraints of reality are implicit. I don't think "it can be done by a human" is satisfied by a method requiring time travel with a very specific form of paradox resolution. It sounds like you're arguing that the Church-Turing thesis is simply worded ambiguously.
1I definitely remember a different Church-Turing Thesis than what you said, and if we kept to realistic limitations of humans, then the set of computable functions is way, way smaller than the traditional view, so that's not really much of a win at all. At any rate, it is usable by a human, mostly because humans are more specific, and critically a Universal Turing Machine can perfectly emulate a human brain, so if we accept the CTC model as valid for Turing Machines, then we need to accept it's validity for humans, since humans are probably just yet another form of Turing Machine.
I will edit the post though, to make it clear what I'm talking about.
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.)
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:
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.
It looks Deutschian CTCs are similar to a computer that can produce all possible outputs in different realities, then selectively destroy the realities that don't solve the problem. It's not surprising that you could solve the halting problem in such a framework.
The way CTC computers actually work is because getting the right answer to a hard problem, assuming we can act on the fundamental degrees of freedom of the universe, means that this is the only logically self-consistent solution, and that getting the wrong answer, or not getting an answer at all is logically inconsistent, and thus can't exist.
Curated and popular this week