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.
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.
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.
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.