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.
I 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.
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.
I 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.
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.
I went to the wikipedia page, and the notion of effective functions was defined like this:
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.
https://en.wikipedia.org/wiki/Effective_method
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.
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.
I 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.