I think you’re getting too hung up on your personal definition of “effectiveness” which doesn’t match what other people mean by it. If you actually wanted to show that Church and Turing’s definition matched your own, I think you should quote their original papers. That said I think it’s very unlikely you’ll find that to be the case, since Turing was well aware that halting oracles existed could be defined and were uncomputable, so clearly he didn’t intend to include them in his definition of effective operations.
Regarding open question 1, I think the answer to “how many functions can we compute in this model” is “all functions”. Since you are allowing arbitrary oracles to be used(by the branching argument), for any given function we can just use an oracle which computes that function.
Turing was well aware that halting oracles existed
Halting oracles do not exist, except Platonically as mathematical objects. We cannot build one. We cannot compute one. What did Turing say that you are describing thus?
That you can define halting oracles and prove they are uncomputable(thus he was well aware that you could mathematically define notions similar to computability which exceed the standard one)
To be fair, while I sort of grant that Turing thought that what we’d call halting oracles may be possible, I still have 2 issues:
The thesis should have been just a definition, and one among some equal definitions, rather than an all-encompassing claim (even then you’d still need to put in some more assumptions for it to work.) This is important, since while I’m fine with it being used as a definition (albeit there are more formal concepts for that), I get the sense that people want to extend it into something larger and more philosophical, and more universal than it is.
Also, the fact that Turing Machines aren’t equivalent under arbitrary extensions is a little important, as you’d need to restrict the way the Turing Machine is extended, if we want to limit our intended models to only allow the computable functions/UTMs as traditionally thought.
He still thought that a halting oracle couldn’t be a machine, and it turns out that intuition was still wrong (I’d have to admit that something weird is happening, because I interpreted that quote very differently from interstice did, since he reacted with a disagreement.)
To be fair, while I sort of grant that Turing thought that what we’d call halting oracles may be possible
If by “thought possible” you mean he was aware of them as a mathematically well-defined concept, there’s no doubt! He was the first to define them!
ETA: I see you reacted “I checked, it’s false” here. That’s wrong—it’s unambiguously the case that Turing was the first to define oracles machines. See here.
I get the sense that people want to extend it into something larger and more philosophical, and more universal than it is
Well, I do think it’s pretty interesting that of all the machines we can apparently build in reality, there exists a universal machine that can emulate them all. That’s a very important fact, and highly non-obvious a priori!
He still thought that a halting oracle couldn’t be a machine, and it turns out that intuition was still wrong
I disagreed because in context I think it’s clear he meant “a machine we can build in reality”. Not “a machine which magically evaluates the problem” or “a machine which flips coins which we assume to always land in such a way that it solves the problem”.
ETA: I see you reacted “I checked, it’s false” here. That’s wrong—it’s unambiguously the case that Turing was the first to define oracles machines. See here.
I looked at the link, and it only states the following:
“Let us suppose we are supplied with some unspecified means of solving number-theoretic problems; a kind of oracle as it were. . . . this oracle . . . cannot be a machine. With the help of the oracle we could form a new kind of machine (call them o-machines), having as one of its fundamental processes that of solving a given number-theoretic problem.”
So as stated, it is still false, as it doesn’t even vaguely suggest a mathematically defined way to show that a halting oracle must exist. It doesn’t nearly work as a definition, and this would require a lot more development before the claim that Turing defined an o-machine mathematically was true. He at best suggests them as maybe possible, but he didn’t do any of the work required to mathematically define a halting oracle.
but he didn’t do any of the work required to mathematically define a halting oracle.
This is unambiguously false. If you want to read a more elaborated version, see Turing’s original paper. To a mathematician, what Turing says there is a definition—the question of how such an oracle could be realized is a totally separate one. I assure you, if you ask any computability theorist, logician, etc., they will agree that this counts as a definition.
As a general note, I don’t think you should be writing articles attempting to “disprove” Turing and Church without understanding the basics of computability theory and how theorists think about definitions and proofs. That way lies madness. I recommend reading an undergraduate textbook on computability theory in detail, doing the exercises as well, and afterwards coming back to this topic. “Computability and Logic” by Boolos is apparently pretty good.
I do not believe Turing actually wanted to do this, in the sense that he wanted to focus on real machines, and I believe that his comments instead suggest that he wanted to focus on ideal machines, rather than machines that could be implemented in reality.
In particular, I’ve generated some quotes that suggest that the idealization was what Turing was focusing on.
Also, I tend to read things conservatively, such that I don’t assume much context beyond what is said, and I don’t think Turing was ever concerned with what we could compute in reality, instead of idealizations.
Well, I do think it’s pretty interesting that of all the machines we can apparently build in reality, there exists a universal machine that can emulate them all. That’s a very important fact, and highly non-obvious a priori!
This is definitely important, but this is more so due to the unbounded space and time allowed, as well as some parallelism.
To make it even better, in this post I showed that you could emulate any arbitrary oracle tape on any input with Turing Machines and thus this lets us emulate even halting oracles, or even let us simulate a universe where humans can calculate exact real numbers.
So this will hold in way more situations than you think, that even if it turns out we can compute the halting problem in real life, there will still be a Universal Turing Machine that simulates it.
It’s impressive and important as a discovery though.
If by “thought possible” you mean he was aware of them as a mathematically well-defined concept, there’s no doubt! He was the first to define them!
Edit: I looked at the link, and it only states the following:
“Let us suppose we are supplied with some unspecified means of
solving number-theoretic problems; a kind of oracle as it were.
. . . this oracle . . . cannot be a machine.
With the help of the oracle we could form a new kind of machine (call them o-machines), having as one of its fundamental
processes that of solving a given number-theoretic problem.”
So as stated, it is still false, as it doesn’t even vaguely suggest a mathematically defined way to show that a halting oracle must exist. It doesn’t nearly work as a definition, and this would require a lot more development before the claim that Turing defined an o-machine mathematically was true. He at best suggests them as maybe possible, but he didn’t do any of the work required to mathematically define a halting oracle.
In general, I think this is IMO my general model of Turing: He had some rather interesting intuitions, but damn did he need a lot of work to make them more formal, whether in the case of the Church-Turing thesis as a definition, or on o-machines, in general things rested way the fuck too much on intuitions, and to a certain extent computability theory has suffered from the overfocus of intuition on the founders, comparable to the issues of geometry because people were too enamored on Euclid’s intuitions.
Original comment: This is overstating what he did. He did think about o-machines, but he never actually made a math model of the o-machines, nor did he ever define it beyond a very basic intuition. Scott Aaronson, Mohammad Bavarian, and Giulio Gueltrini actually did the work to create an o-machine constructively, and even if we allow non-constructive definitions, Turing and Church was definitely very far from actually showing that a halting oracle exists. That one had to be done by other researchers.
While he was aware of the possibility of o-machines, the problem here that arises is that given Turing’s focus on idealizations of how humans calculated, that other people needed to be much more careful in their claims, because you cannot make a universal claim that holds without also addressing how the purported counterexamples don’t hold up.
And while Turing gave some intuition for why the Church-Turing Thesis should hold, intuitions are not proof, for the same reasons that the intuitive notion of continuous functions always being differentiable was disproved.
In particular, I’ve generated some quotes that suggest that the idealization was what Turing was focusing on.
Yes, Turing machines are an idealization, but they’re meant to be an idealization of processes of computation we can carry out in the real world. That’s why computability is a useful notion to study, it corresponds to something we care about in reality. In contrast, a notion of computation which includes time travel or arbitrary oracles is less useful, because as far as we know those don’t exist. Regarding the point about time boundedness, yes Turing-computability does not exactly correspond to things we will be able to compute in reality(probably), but it’s a lot closer to reality than models of computation with oracles or time travel. Similarly, the Earth is not exactly spherical, but models which treat the Earth as spherical are a lot closer to reality than models which treat space as having 7 dimensions.
And while Turing gave some intuition for why the Church-Turing Thesis should hold, intuitions are not proof
I think this might be the core issue with your argument: the Church-Turing thesis is not the sort of thing you can prove or disprove mathematically. It’s an attempt at matching an informal concept with a set of axioms. You can’t prove or disprove a set of axioms, you can just choose sets which are more or less useful based on philosophical argument, empirical evidence, etc. Everybody who studies computability is aware that you can define alternative models of computation and study their properties, it’s just that those other models are considered less important because they can’t actually be built. If you want to convince people to change their notion of computability, you have to argue that your new definition is more useful for modeling something in reality they care about, trying to pull a ‘gotcha’ based on a list of requirements you made up yourself is pointless.
Yes, Turing machines are an idealization, but they’re meant to be an idealization of processes of computation we can carry out in the real world. That’s why computability is a useful notion to study, it corresponds to something we care about in reality.
The problem is by idealizing that away, we have made it much less useful. Universal Turing Machines as Turing defined them are basically in a similar class to ideas like arbitrary oracles or time travel: they require assumptions that basic physical constraints are fundamentally wrong.
In other words, idealization buys us too much power.
In particular, I disagree with this heavily:
Regarding the point about time boundedness, yes Turing-computability does not exactly correspond to things we will be able to compute in reality(probably), but it’s a lot closer to reality than models of computation with oracles or time travel.
Yes, technically UTMs are a little better at modeling computation, but it’s still much much farther than likely reality (this is so here), because it relies on certain assumptions being wrong, and any way this happens would likely imply that the other models of computation suddenly become more plausible. It’s a little less wrong, but there are other models which are way more accurate. In other words, the idealization is so unrealistic
If you want to focus on real life computation without having to leave theory, computational complexity already does that job. If you want to focus on near future reality, then complexity theory is best while not having to deal with a lot of messiness.
the Church-Turing thesis is not the sort of thing you can prove or disprove mathematically. It’s an attempt at matching an informal concept with a set of axioms.
I have two things to say here:
While Euclid’s axioms of geometry weren’t disproven, the intuitive notion that this represented the only valid/true geometry was broken, and I see a similar issue here.
Even then, there are other ways to get to the UTM using more formal definitions, and in the case where you just want to focus on UTMs, that’s fine, but don’t try to imply that it’s somehow universal/the only true model etc.
Also, how you do this: “It’s an attempt at matching an informal concept with a set of axioms.” can matter a lot, and while I expect some intuitions to focus on the UTM, others won’t, and instead get drastically different results.
I think a big difference between us is that I don’t expect computability theory to model our reality at all, just what is possible in the multiverse of logic, whereas you do expect computability theory to model our reality, and thus I’m fine with many of my results even if they can’t be applied in reality, since I generally think that even the computable stuff isn’t useful at all in applied reality, and thus I usually focus on arbitrary idealizations when focusing on computability theory.
You disagree with that because you do expect computability theory to model our reality.
If I wanted to model computational reality, I’d use very different tools than computability theory to model it.
Edit:
Everybody who studies computability is aware that you can define alternative models of computation and study their properties,
It certainly wasn’t obvious to Turing, Church and Godel et al. I can definitely agree that modern people studying computability theory may understand this, at least implicitly, but I don’t think that happened with the original founders of computability theory, and the link you gave me is quite insufficient, in that ignoring the other falsities that Turing made in the quote, it didn’t even define the concept beyond a very basic level.
For the purposes of this post, we are not much concerned about the constraints of our specific reality, for 3 reasons:
If we accept this argument, then it’s unlikely that a true Universal Turing Machine exists in real life either, because it doesn’t have time bounds or memory bounds. So we are already idealizing things away to make it work at all.
If we did use real humans computing/counting things, rather than idealized human computing/counting things, then the problem becomes the fact that we only have a finite, constant memory and time, and the functions/algorithms that are in the computable set as defined by a UTM does not collapse to the set of functions calculable by a human. If they did, such that human people in real life could calculate all the computable functions in constant time and memory, that would violate the time and space hierarchy theorems. I literally addressed this.
While we think that halting oracles can’t exist, and there are many good reasons to believe that, it doesn’t totally mean that we figured things out yet, and while I basically agree that it’s unlikely, I am unwilling to make very firm conclusions about the very far future, including this one.
Even then, I’m still a bit mystified, in that I don’t understand why people treat it like an absolute notion that applies to all computational models, rather than simply a definition, and one that can be replaced by other equivalent or different definitions like this quote below:
Gödel said that “the great importance … [of] Turing’s computability” is
largely due to the fact that with this concept one has for the first time succeeded in giving an absolute definition of an interesting epistemological notion, i.e., one not depending on the formalism chosen. (Gödel 1946: 150)
or like this quote below:
Gödel also said:
The resulting definition of the concept of mechanical by the sharp concept of “performable by a Turing machine” is both correct and unique. … Moreover it is absolutely impossible that anybody who understands the question and knows Turing’s definition should decide for a different concept. (Quoted in Wang 1996: 203)
Putting it less politely, my biggest issue is a motte and bailey is going on, where people want to defend the correct motte of the Church-Turing thesis as a definition, albeit there are other equivalent ones, but people want to go beyond that and defend the incorrect bailey that it’s absolute/universal/the only valid definition of something, similar to how people thought the intuitive definition of Euclidean Geometry was the only possible valid geometry, at least implicitly.
I will check out Turing and Church’s papers, though I will say that for the conditions 2.5 and 2.6, they’re there to express two ideas below:
2.5 was essentially a statement explicitly saying that no other constraints to the problem were added, other than the constraints above.
2.6 was not Turing’s idea or problem, and instead it’s a modern problem, I’ll have to edit the post to say that this is not something that Turing thought about.
And condition 2.3 is essentially replacing the rigorousness of something instead of creativity by instead asking whether a single algorithm can solve arbitrary instances of a problem, like in a decision problem where the answers are yes or no, I require the algorithm to always say yes if it’s in the set, and no if it’s not in the set, and that this must be doable on arbitrary instances of a problem. in other words given that algorithm applied to the problem, you don’t need to think about it, you can just be rigorous, in the sense that you apply the same algorithm for arbitrary instances of a problem, and can follow it by rote, and you don’t need to have a different algorithm.
Regarding open question 1, I think the answer to “how many functions can we compute in this model” is “all functions”. Since you are allowing arbitrary oracles to be used (by the branching argument), for any given function we can just use an oracle which computes that function.
This seems like it’s instead an answer to Open Question 2, in that we can simulate all oracle tapes on all inputs, finite or infinite, which is I think equivalent to solving all the functions from N to N, and that’s the set of all programs. I was also asking for an upper bound, too if you can supply it, but I’ll take it as a partial answer.
Is there a reason that allowing arbitrary extensions to the UTM that respect the constraints of an effective function does the same thing? That is, if we give the UTM arbitrary extensions, can we too get it to solve say all the functions from N to N via arbitrary extensions of the UTM model, and is it upper bounded by all functions from N to N?
Edit: I’ve decided to share some preliminary results of my checking, and I already see some issues below:
For example, this statement:
That said I think it’s very unlikely you’ll find that to be the case, since Turing was well aware that halting oracles existed, so clearly he didn’t intend to include them in his definition of effective operations.
Is correct, but misses major nuance, and importantly assumes it’s not a machine. That’s a problem, because without more assumptions, you can’t exclude halting oracles from your definition of effective operations. He assumed that there could be an unspecified oracle, but the problem is in the statement below, he falsely believes it’s not a machine that calculates effective functions, when it is, and critically he didn’t know that you could make the model more concrete into an actual machine. To be clear, I don’t blame Turing too much, as the results in the post weren’t known, and Church and Turing made the entire foundation from scratch, so it was inevitable that mistakes would be made.
Let us suppose that we are supplied with some unspecified means of solving number-theoretic problems; a kind of oracle as it were. We shall not go any further into the nature of this oracle apart from saying that it
cannot be a machine.
This is from the paper Systems of Logic Based On Ordinals, link is below:
I think you’re getting too hung up on your personal definition of “effectiveness” which doesn’t match what other people mean by it. If you actually wanted to show that Church and Turing’s definition matched your own, I think you should quote their original papers. That said I think it’s very unlikely you’ll find that to be the case, since Turing was well aware that halting oracles
existedcould be defined and were uncomputable, so clearly he didn’t intend to include them in his definition of effective operations.Regarding open question 1, I think the answer to “how many functions can we compute in this model” is “all functions”. Since you are allowing arbitrary oracles to be used(by the branching argument), for any given function we can just use an oracle which computes that function.
Halting oracles do not exist, except Platonically as mathematical objects. We cannot build one. We cannot compute one. What did Turing say that you are describing thus?
That you can define halting oracles and prove they are uncomputable(thus he was well aware that you could mathematically define notions similar to computability which exceed the standard one)
To be fair, while I sort of grant that Turing thought that what we’d call halting oracles may be possible, I still have 2 issues:
The thesis should have been just a definition, and one among some equal definitions, rather than an all-encompassing claim (even then you’d still need to put in some more assumptions for it to work.) This is important, since while I’m fine with it being used as a definition (albeit there are more formal concepts for that), I get the sense that people want to extend it into something larger and more philosophical, and more universal than it is.
Also, the fact that Turing Machines aren’t equivalent under arbitrary extensions is a little important, as you’d need to restrict the way the Turing Machine is extended, if we want to limit our intended models to only allow the computable functions/UTMs as traditionally thought.
He still thought that a halting oracle couldn’t be a machine, and it turns out that intuition was still wrong (I’d have to admit that something weird is happening, because I interpreted that quote very differently from interstice did, since he reacted with a disagreement.)
If by “thought possible” you mean he was aware of them as a mathematically well-defined concept, there’s no doubt! He was the first to define them!
ETA: I see you reacted “I checked, it’s false” here. That’s wrong—it’s unambiguously the case that Turing was the first to define oracles machines. See here.
Well, I do think it’s pretty interesting that of all the machines we can apparently build in reality, there exists a universal machine that can emulate them all. That’s a very important fact, and highly non-obvious a priori!
I disagreed because in context I think it’s clear he meant “a machine we can build in reality”. Not “a machine which magically evaluates the problem” or “a machine which flips coins which we assume to always land in such a way that it solves the problem”.
I looked at the link, and it only states the following:
“Let us suppose we are supplied with some unspecified means of solving number-theoretic problems; a kind of oracle as it were. . . . this oracle . . . cannot be a machine. With the help of the oracle we could form a new kind of machine (call them o-machines), having as one of its fundamental processes that of solving a given number-theoretic problem.”
So as stated, it is still false, as it doesn’t even vaguely suggest a mathematically defined way to show that a halting oracle must exist. It doesn’t nearly work as a definition, and this would require a lot more development before the claim that Turing defined an o-machine mathematically was true. He at best suggests them as maybe possible, but he didn’t do any of the work required to mathematically define a halting oracle.
This is unambiguously false. If you want to read a more elaborated version, see Turing’s original paper. To a mathematician, what Turing says there is a definition—the question of how such an oracle could be realized is a totally separate one. I assure you, if you ask any computability theorist, logician, etc., they will agree that this counts as a definition.
As a general note, I don’t think you should be writing articles attempting to “disprove” Turing and Church without understanding the basics of computability theory and how theorists think about definitions and proofs. That way lies madness. I recommend reading an undergraduate textbook on computability theory in detail, doing the exercises as well, and afterwards coming back to this topic. “Computability and Logic” by Boolos is apparently pretty good.
I decided to check it, and for now, I’ll accept the definition, even with my issues.
Okay, a crux that I have can be stated as this:
I do not believe Turing actually wanted to do this, in the sense that he wanted to focus on real machines, and I believe that his comments instead suggest that he wanted to focus on ideal machines, rather than machines that could be implemented in reality.
In particular, I’ve generated some quotes that suggest that the idealization was what Turing was focusing on.
Also, I tend to read things conservatively, such that I don’t assume much context beyond what is said, and I don’t think Turing was ever concerned with what we could compute in reality, instead of idealizations.
This is definitely important, but this is more so due to the unbounded space and time allowed, as well as some parallelism.
To make it even better, in this post I showed that you could emulate any arbitrary oracle tape on any input with Turing Machines and thus this lets us emulate even halting oracles, or even let us simulate a universe where humans can calculate exact real numbers.
So this will hold in way more situations than you think, that even if it turns out we can compute the halting problem in real life, there will still be a Universal Turing Machine that simulates it.
It’s impressive and important as a discovery though.
Edit: I looked at the link, and it only states the following:
So as stated, it is still false, as it doesn’t even vaguely suggest a mathematically defined way to show that a halting oracle must exist. It doesn’t nearly work as a definition, and this would require a lot more development before the claim that Turing defined an o-machine mathematically was true. He at best suggests them as maybe possible, but he didn’t do any of the work required to mathematically define a halting oracle.
In general, I think this is IMO my general model of Turing: He had some rather interesting intuitions, but damn did he need a lot of work to make them more formal, whether in the case of the Church-Turing thesis as a definition, or on o-machines, in general things rested way the fuck too much on intuitions, and to a certain extent computability theory has suffered from the overfocus of intuition on the founders, comparable to the issues of geometry because people were too enamored on Euclid’s intuitions.
Original comment: This is overstating what he did. He did think about o-machines, but he never actually made a math model of the o-machines, nor did he ever define it beyond a very basic intuition. Scott Aaronson, Mohammad Bavarian, and Giulio Gueltrini actually did the work to create an o-machine constructively, and even if we allow non-constructive definitions, Turing and Church was definitely very far from actually showing that a halting oracle exists. That one had to be done by other researchers.
While he was aware of the possibility of o-machines, the problem here that arises is that given Turing’s focus on idealizations of how humans calculated, that other people needed to be much more careful in their claims, because you cannot make a universal claim that holds without also addressing how the purported counterexamples don’t hold up.
And while Turing gave some intuition for why the Church-Turing Thesis should hold, intuitions are not proof, for the same reasons that the intuitive notion of continuous functions always being differentiable was disproved.
Yes, Turing machines are an idealization, but they’re meant to be an idealization of processes of computation we can carry out in the real world. That’s why computability is a useful notion to study, it corresponds to something we care about in reality. In contrast, a notion of computation which includes time travel or arbitrary oracles is less useful, because as far as we know those don’t exist. Regarding the point about time boundedness, yes Turing-computability does not exactly correspond to things we will be able to compute in reality(probably), but it’s a lot closer to reality than models of computation with oracles or time travel. Similarly, the Earth is not exactly spherical, but models which treat the Earth as spherical are a lot closer to reality than models which treat space as having 7 dimensions.
I think this might be the core issue with your argument: the Church-Turing thesis is not the sort of thing you can prove or disprove mathematically. It’s an attempt at matching an informal concept with a set of axioms. You can’t prove or disprove a set of axioms, you can just choose sets which are more or less useful based on philosophical argument, empirical evidence, etc. Everybody who studies computability is aware that you can define alternative models of computation and study their properties, it’s just that those other models are considered less important because they can’t actually be built. If you want to convince people to change their notion of computability, you have to argue that your new definition is more useful for modeling something in reality they care about, trying to pull a ‘gotcha’ based on a list of requirements you made up yourself is pointless.
The problem is by idealizing that away, we have made it much less useful. Universal Turing Machines as Turing defined them are basically in a similar class to ideas like arbitrary oracles or time travel: they require assumptions that basic physical constraints are fundamentally wrong.
In other words, idealization buys us too much power.
In particular, I disagree with this heavily:
Yes, technically UTMs are a little better at modeling computation, but it’s still much much farther than likely reality (this is so here), because it relies on certain assumptions being wrong, and any way this happens would likely imply that the other models of computation suddenly become more plausible. It’s a little less wrong, but there are other models which are way more accurate. In other words, the idealization is so unrealistic
If you want to focus on real life computation without having to leave theory, computational complexity already does that job. If you want to focus on near future reality, then complexity theory is best while not having to deal with a lot of messiness.
I have two things to say here:
While Euclid’s axioms of geometry weren’t disproven, the intuitive notion that this represented the only valid/true geometry was broken, and I see a similar issue here.
Even then, there are other ways to get to the UTM using more formal definitions, and in the case where you just want to focus on UTMs, that’s fine, but don’t try to imply that it’s somehow universal/the only true model etc.
Also, how you do this: “It’s an attempt at matching an informal concept with a set of axioms.” can matter a lot, and while I expect some intuitions to focus on the UTM, others won’t, and instead get drastically different results.
I think a big difference between us is that I don’t expect computability theory to model our reality at all, just what is possible in the multiverse of logic, whereas you do expect computability theory to model our reality, and thus I’m fine with many of my results even if they can’t be applied in reality, since I generally think that even the computable stuff isn’t useful at all in applied reality, and thus I usually focus on arbitrary idealizations when focusing on computability theory.
You disagree with that because you do expect computability theory to model our reality.
If I wanted to model computational reality, I’d use very different tools than computability theory to model it.
Edit:
It certainly wasn’t obvious to Turing, Church and Godel et al. I can definitely agree that modern people studying computability theory may understand this, at least implicitly, but I don’t think that happened with the original founders of computability theory, and the link you gave me is quite insufficient, in that ignoring the other falsities that Turing made in the quote, it didn’t even define the concept beyond a very basic level.
Other researchers had to do this.
For the purposes of this post, we are not much concerned about the constraints of our specific reality, for 3 reasons:
If we accept this argument, then it’s unlikely that a true Universal Turing Machine exists in real life either, because it doesn’t have time bounds or memory bounds. So we are already idealizing things away to make it work at all.
If we did use real humans computing/counting things, rather than idealized human computing/counting things, then the problem becomes the fact that we only have a finite, constant memory and time, and the functions/algorithms that are in the computable set as defined by a UTM does not collapse to the set of functions calculable by a human. If they did, such that human people in real life could calculate all the computable functions in constant time and memory, that would violate the time and space hierarchy theorems. I literally addressed this.
While we think that halting oracles can’t exist, and there are many good reasons to believe that, it doesn’t totally mean that we figured things out yet, and while I basically agree that it’s unlikely, I am unwilling to make very firm conclusions about the very far future, including this one.
Even then, I’m still a bit mystified, in that I don’t understand why people treat it like an absolute notion that applies to all computational models, rather than simply a definition, and one that can be replaced by other equivalent or different definitions like this quote below:
or like this quote below:
Putting it less politely, my biggest issue is a motte and bailey is going on, where people want to defend the correct motte of the Church-Turing thesis as a definition, albeit there are other equivalent ones, but people want to go beyond that and defend the incorrect bailey that it’s absolute/universal/the only valid definition of something, similar to how people thought the intuitive definition of Euclidean Geometry was the only possible valid geometry, at least implicitly.
I will check out Turing and Church’s papers, though I will say that for the conditions 2.5 and 2.6, they’re there to express two ideas below:
2.5 was essentially a statement explicitly saying that no other constraints to the problem were added, other than the constraints above.
2.6 was not Turing’s idea or problem, and instead it’s a modern problem, I’ll have to edit the post to say that this is not something that Turing thought about.
And condition 2.3 is essentially replacing the rigorousness of something instead of creativity by instead asking whether a single algorithm can solve arbitrary instances of a problem, like in a decision problem where the answers are yes or no, I require the algorithm to always say yes if it’s in the set, and no if it’s not in the set, and that this must be doable on arbitrary instances of a problem. in other words given that algorithm applied to the problem, you don’t need to think about it, you can just be rigorous, in the sense that you apply the same algorithm for arbitrary instances of a problem, and can follow it by rote, and you don’t need to have a different algorithm.
This seems like it’s instead an answer to Open Question 2, in that we can simulate all oracle tapes on all inputs, finite or infinite, which is I think equivalent to solving all the functions from N to N, and that’s the set of all programs. I was also asking for an upper bound, too if you can supply it, but I’ll take it as a partial answer.
Is there a reason that allowing arbitrary extensions to the UTM that respect the constraints of an effective function does the same thing? That is, if we give the UTM arbitrary extensions, can we too get it to solve say all the functions from N to N via arbitrary extensions of the UTM model, and is it upper bounded by all functions from N to N?
Edit: I’ve decided to share some preliminary results of my checking, and I already see some issues below:
For example, this statement:
Is correct, but misses major nuance, and importantly assumes it’s not a machine. That’s a problem, because without more assumptions, you can’t exclude halting oracles from your definition of effective operations. He assumed that there could be an unspecified oracle, but the problem is in the statement below, he falsely believes it’s not a machine that calculates effective functions, when it is, and critically he didn’t know that you could make the model more concrete into an actual machine. To be clear, I don’t blame Turing too much, as the results in the post weren’t known, and Church and Turing made the entire foundation from scratch, so it was inevitable that mistakes would be made.
This is from the paper Systems of Logic Based On Ordinals, link is below:
https://pure.mpg.de/rest/items/item_2403325_2/component/file_2403324/content
There may be other problems, but that’s just the first problem I found.