3 ms·
Ok, for the sake of argument I will agree with you on "it's not practically useful" (for now, at least). But I will disagree with you on "it's not theoreticall
by wizeman 4y ago
Ok, for the sake of argument I will agree with you on "it's not practically useful" (for now, at least).
But I will disagree with you on "it's not theoretically interesting".
Almost the entire field of computer science is based on Turing machines and on the following definition of "computable function": "computable functions are exactly the functions that can be calculated using a mechanical calculation device given unlimited amounts of time and storage space".
Now, of course, I can argue that this definition of computable function and Turing machines are ridiculous and will lead to ridiculous conclusions, but I think I already did that elsewhere, so let's move on.
Now imagine that instead of Turing machines, computer science would use deterministic linear bounded automatons (deterministic LBAs, which are the closest finite approximation of Turing machines).
And instead of that definition of computable function, let's use this one: "computable functions are exactly the functions that can be calculated using a mechanical calculation device given unlimited amounts of time but limited amounts of storage space".
What would be different in computer science?
Well, at least the following would be different:
1. The Halting problem becomes decidable
2. Rice's theorem becomes false, which means we can decide properties about computable functions.
3. As an example, perhaps you're familiar with the busy beaver problem, which is defined over Turing machines and is a function of N, where N is the number of states of the Turing machine. It is impossible to create an algorithm to decide whether a Turing machine is a busy beaver.
If you defined the busy beaver problem over deterministic linear bounded automatons (LBAs) adding an additional parameter K for the length of the tape, then suddenly it becomes possible to create an algorithm that determines whether a given LBA is a busy beaver!
Similarly, the busy beaver function is defined over Turing machines and is a function of N (where N = number of states).
In my redesigned field of computer science, the busy beaver function would also be defined over deterministic LBAs and would be a function of N and K, where N is the same as above, and K is the length of the LBA tape.
This would also have interesting consequences.
First of all, the busy beaver function would become a computable function instead of non-computable.
It would also become more meaningful in the real world, because we could answer the question: my computer has K bits, how many 1 bits could a halting program with N states write?
And you would still be able to answer the original questions about the original busy beaver, which you would realize is not a computing question, but it is actually a mathematical question concerning infinite Ks, which is: "for a fixed N and for all K, what is max(busy_beaver_function(N, K))?".
There's also an interesting additional mathematical question that would come up: for all N and for all K, is it true that if busy_beaver_function(N, K) = busy_beaver_function(N, K+1) then there is no J such that busy_beaver_function(N, J) > busy_beaver_function(N, K)?
In other words, if you increase K and the busy beaver function gives you the same result, does that mean that there is no point in increasing K any more because no higher K will give you a larger result?
What if you step-wise increase K by multiplying by 2 instead of adding 1?
Presumably, the above questions have to be false, otherwise the original busy beaver function would be computable, but it would still be interesting to have separate proofs, which could lead to new insights, especially if you didn't know that the original busy beaver function was non-computable!
All sorts of similar reasoning would apply to all sorts of other problems. Many undecidable problems become decidable. Many non-computable functions would become computable. Many questions that were previously about Turing machines suddenly become more meaningful for actual computers. You would naturally ask more interesting (finite and infinite) questions as functions of state size.
And, you could still answer the same mathematical questions about them (that we currently use Turing machines for), just by introducing a "for all" quantifier in the state size. Which would also make many things a lot clearer.
I could go on and on.
(To be clear: a computable function does not imply that it can be efficiently computed, i.e. computed within a reasonable amount of time. This is true both for the current definition and my definition).