Great, “unbounded” isn’t the same as “infinite”, but in fact all physically realizable computers are bounded. There’s a specific finite amount of tape available. You cannot in fact just go down to the store and buy any amount of tape you want. There isn’t unlimited time either. Nor unlimited energy. Nor will the machine tolerate unlimited wear.
Yes, but that’s not relevant to the definition of Turing equivalence/completeness/universality.
The question isn’t if the specific computer at your hands can solve all Turing-computable problems, but rather if we had the ability to scale a computer’s memory, time and reliability indefinitely, could we solve the problem on an unbounded input and output domain without changing the code/descriptor?
And for a lot of popular programming languages, like Lisp or Lambda Calculus, this is true.
For that matter, real computers can’t even address unlimited storage, nor is there a place to plug it in. You can’t in fact write a 6502 assembly language program to solve a problem that requires more than 64kiB of memory. Nor an assembly language program for any physically realized computer architecture, ever, that can actually use unbounded memory.
My guess is that the issues are fundamentally because writing an assembly programming language that used arbitrary precision arithmetic/arbitrary precision operations would make programs a whole lot slower by constant factors, so there is no incentive to make assembly programming language that is Turing-complete, and at any rate is already duplicative of the high-level programming languages like Java or Lisp, and you can write a program in Lisp that duplicates the assembly’s functionality.
And at any rate, there exist assembly languages that are Turing Complete, so this is irrelevant.
On implementation issues like fixed-precision vs arbitrary precision arithmetic:
Before we dive in, let me clear something up. My critiques below are not about hardware limitations or implementation. Some models rely on numerical values with arbitrary precision to ‘attend’ to tokens in the sequence. That’s fine. It’s common to use 64-bit floating point precision types, which are incapable of representing arbitrary precision values, but that’s an implementation choice separate from the abstract model of a transformer. In the same way that you can switch to a computer with more memory, you can always switch to higher fixed-precision to run a transformer on something that needs that extra boost to execute properly. You can even abandon the floating-point format altogether and store numbers as strings representing the numerator and denominator. As long as you don’t rely on infinite-precision, arbitrary finite precision is easily implementable in a digital representation scheme.
There are always going to be Turing-computable problems that your physical device cannot solve. Playing word games, or twisting what you’ll accept as being Turing-equivalent, doesn’t change that fundamental limitation. Actual physics strictly limit the real usefulness of the Turing abstraction. Use it when it makes sense, but there’s no point in pretending it applies to physical computers in any strong way.
The main value of the Turing abstraction in our universe is that it isolates where the bottleneck actually is, and that the bottleneck is not about algorithms/developing new codes to solve specific problems of specific input sizes (with the enormous caveat that if we care about how efficient a program is, and don’t just care about whether we can solve a problem, then algorithmic considerations become relevant), but rather that the bottleneck is energy, which gives us memory, time and reliability.
And from the perspective of the early 20th century, this was no small feat.
Yes, but that’s not relevant to the definition of Turing equivalence/completeness/universality.
Every Turing machine definition I’ve ever seen says that the tape has to be truly unbounded. How that’s formalized varies, but it always carries the sense that the program doesn’t ever have to worry about running out of tape. And every definition of Turing equivalence I’ve ever seen boils down to “can do any computation a Turing machine can do, with at most a bounded speedup or slowdown”. Which means that programs on Turing equivalent computer must not have to worry about running out of storage.
You can’t in fact build a computer that can run any arbitrary program and never run out of storage.
One of the explicitly stated conditions of the definition is not met. How is that not relevant to the definition?
The question isn’t if the specific computer at your hands
Your title says “finite physical device”. Any finite physical device (or at least any constructible finite physical device) can at least in principle be “the specific computer at your hands”. For a finite physical device to be Turing equivalent, there would have to be a specific finite physical device that actually was Turing-equivalent. And no such device can ever actually be constructed. In fact no such device could exist even if it popped into being without even having to be constructed.
can solve all Turing-computable problems, but rather if we had the ability to scale a computer’s memory, time and reliability indefinitely, could we solve the problem on an unbounded input and output domain without changing the code/descriptor?
I don’t think that is the question, and perhaps more importantly I don’t think that’s an interesting question. You don’t have that ability, you won’t get that ability, and you’ll never get close enough that it’s practical to ignore the limitation. So who cares?
… and if you’re going to talk in terms of fundamental math definitions that everybody uses, I think you have to stick to what they conventionally mean.
And for a lot of popular programming languages, like Lisp or Lambda Calculus, this is true.
Lisp is obviously Turing-complete. Any Lisp interpreter actually realized on any finite physical computer isn’t and can’t ever be. If you keep sticking more and more cells onto a list, eventually the Lisp abstraction will be violated by the program crashing with an out-of-memory error. You can’t actually implement “full Lisp” in the physical world.
On X86 being Turing Complete in at least 3 ways:
OK, it’s possible that there’s some subset of the X86 machine language that’s Turing equivalent the same way Lisp is. I’m not going to go and try to figure out whatever hackery the examples do, since it’s probably very complicated and will probably never be of any actual use. But if there is, it’s still not Turing equivalent as actually implemented in any actual device.
Any actual physically constructed X86 computer will have a finite number of possible states, no matter what operations you use to manipulate them. There are only so many address wires coming out of the chip. There are only so many registers, memory cells, or whatever. Even if you put a Turing tape reader on it as a peripheral, there’s still a hard limit on how much tape it can actually have.
If you write a program that ignores that reality, and put it in an actual X86 computer, you won’t have created a Turing complete physical computer. When the input gets to a certain size, the program just won’t work. The physical hardware can’t support pushing the abstract language past a certain limit.
In the same way that you can switch to a computer with more memory, you can always switch to higher fixed-precision to run a transformer on something that needs that extra boost to execute properly.
No, you can’t. It’s possible to have a problem that requires so much precision that you can’t physically construct enough memory to hold even a single number.
(with the enormous caveat that if we care about how efficient a program is, and don’t just care about whether we can solve a problem, then algorithmic considerations become relevant),
A useful definition of “can” has to take efficiency into account, because there are some resources you actually can’t provide. There’s not a lot of point in saying you “can” solve a problem when you really have no hope of applying the needed resources.
We use that practically all the time. That’s how cryptography works: you assume that your adversary won’t be able to do more than N operations in X time, where X is how long the cryptography has to be effective for.
the bottleneck is energy, which gives us memory, time and reliability.
Maybe, although I don’t think we can at present turn energy in just any form into any of the above, and I’m not sure that, in principle, unlimited energy translates into unlimited anything else. If I have some huge amount of energy in some tiny space, I have a black hole, not a computer.
And from the perspective of the early 20th century, this was no small feat.
… but even if that were true, it wouldn’t make finite physical computers Turing equivalent.
Every Turing machine definition I’ve ever seen says that the tape has to be truly unbounded. How that’s formalized varies, but it always carries the sense that the program doesn’t ever have to worry about running out of tape. And every definition of Turing equivalence I’ve ever seen boils down to “can do any computation a Turing machine can do, with at most a bounded speedup or slowdown”. Which means that programs on Turing equivalent computer must not have to worry about running out of storage.
You can’t in fact build a computer that can run any arbitrary program and never run out of storage.
One of the explicitly stated conditions of the definition is not met. How is that not relevant to the definition?
Yes, this is correct, with the important caveat that the memory is unbounded by the systems descriptor/programming language, not the physical laws or anything else which is the key thing you missed.
Essentially speaking, it’s asking if modern computers can cope with arbitrary extensions to their memory and time and reliability without requiring us to write new programming languages/coding, not if a specific computer at a specified memory and time limit is Turing complete.
Looking at your comment more, I think this disagreement is basically a definitional dispute, in a way, because I allow machines that are limited by the laws of physics but are not limited by their systems descriptor/programming language to be Turing complete, while you do not, and I noticed we had different definitions that led to different results.
I suspect this was due to focusing on different things, where I was focused on the extensibility of the computer concept as well as the more theoretical aspects, whereas you were much more focused on the low level situation.
A crux might be that I definitely believe that given an unlimited energy generator, it is very easy to to create a universal computer out of it, and I think energy is much, much closer to a universal currency than you do.
Yes, but that’s not relevant to the definition of Turing equivalence/completeness/universality.
The question isn’t if the specific computer at your hands can solve all Turing-computable problems, but rather if we had the ability to scale a computer’s memory, time and reliability indefinitely, could we solve the problem on an unbounded input and output domain without changing the code/descriptor?
And for a lot of popular programming languages, like Lisp or Lambda Calculus, this is true.
My guess is that the issues are fundamentally because writing an assembly programming language that used arbitrary precision arithmetic/arbitrary precision operations would make programs a whole lot slower by constant factors, so there is no incentive to make assembly programming language that is Turing-complete, and at any rate is already duplicative of the high-level programming languages like Java or Lisp, and you can write a program in Lisp that duplicates the assembly’s functionality.
And at any rate, there exist assembly languages that are Turing Complete, so this is irrelevant.
More here:
On X86 being Turing Complete in at least 3 ways:
On implementation issues like fixed-precision vs arbitrary precision arithmetic:
https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic
The main value of the Turing abstraction in our universe is that it isolates where the bottleneck actually is, and that the bottleneck is not about algorithms/developing new codes to solve specific problems of specific input sizes (with the enormous caveat that if we care about how efficient a program is, and don’t just care about whether we can solve a problem, then algorithmic considerations become relevant), but rather that the bottleneck is energy, which gives us memory, time and reliability.
And from the perspective of the early 20th century, this was no small feat.
Every Turing machine definition I’ve ever seen says that the tape has to be truly unbounded. How that’s formalized varies, but it always carries the sense that the program doesn’t ever have to worry about running out of tape. And every definition of Turing equivalence I’ve ever seen boils down to “can do any computation a Turing machine can do, with at most a bounded speedup or slowdown”. Which means that programs on Turing equivalent computer must not have to worry about running out of storage.
You can’t in fact build a computer that can run any arbitrary program and never run out of storage.
One of the explicitly stated conditions of the definition is not met. How is that not relevant to the definition?
Your title says “finite physical device”. Any finite physical device (or at least any constructible finite physical device) can at least in principle be “the specific computer at your hands”. For a finite physical device to be Turing equivalent, there would have to be a specific finite physical device that actually was Turing-equivalent. And no such device can ever actually be constructed. In fact no such device could exist even if it popped into being without even having to be constructed.
I don’t think that is the question, and perhaps more importantly I don’t think that’s an interesting question. You don’t have that ability, you won’t get that ability, and you’ll never get close enough that it’s practical to ignore the limitation. So who cares?
… and if you’re going to talk in terms of fundamental math definitions that everybody uses, I think you have to stick to what they conventionally mean.
Lisp is obviously Turing-complete. Any Lisp interpreter actually realized on any finite physical computer isn’t and can’t ever be. If you keep sticking more and more cells onto a list, eventually the Lisp abstraction will be violated by the program crashing with an out-of-memory error. You can’t actually implement “full Lisp” in the physical world.
OK, it’s possible that there’s some subset of the X86 machine language that’s Turing equivalent the same way Lisp is. I’m not going to go and try to figure out whatever hackery the examples do, since it’s probably very complicated and will probably never be of any actual use. But if there is, it’s still not Turing equivalent as actually implemented in any actual device.
Any actual physically constructed X86 computer will have a finite number of possible states, no matter what operations you use to manipulate them. There are only so many address wires coming out of the chip. There are only so many registers, memory cells, or whatever. Even if you put a Turing tape reader on it as a peripheral, there’s still a hard limit on how much tape it can actually have.
If you write a program that ignores that reality, and put it in an actual X86 computer, you won’t have created a Turing complete physical computer. When the input gets to a certain size, the program just won’t work. The physical hardware can’t support pushing the abstract language past a certain limit.
No, you can’t. It’s possible to have a problem that requires so much precision that you can’t physically construct enough memory to hold even a single number.
A useful definition of “can” has to take efficiency into account, because there are some resources you actually can’t provide. There’s not a lot of point in saying you “can” solve a problem when you really have no hope of applying the needed resources.
We use that practically all the time. That’s how cryptography works: you assume that your adversary won’t be able to do more than N operations in X time, where X is how long the cryptography has to be effective for.
Maybe, although I don’t think we can at present turn energy in just any form into any of the above, and I’m not sure that, in principle, unlimited energy translates into unlimited anything else. If I have some huge amount of energy in some tiny space, I have a black hole, not a computer.
… but even if that were true, it wouldn’t make finite physical computers Turing equivalent.
Yes, this is correct, with the important caveat that the memory is unbounded by the systems descriptor/programming language, not the physical laws or anything else which is the key thing you missed.
Essentially speaking, it’s asking if modern computers can cope with arbitrary extensions to their memory and time and reliability without requiring us to write new programming languages/coding, not if a specific computer at a specified memory and time limit is Turing complete.
Looking at your comment more, I think this disagreement is basically a definitional dispute, in a way, because I allow machines that are limited by the laws of physics but are not limited by their systems descriptor/programming language to be Turing complete, while you do not, and I noticed we had different definitions that led to different results.
I suspect this was due to focusing on different things, where I was focused on the extensibility of the computer concept as well as the more theoretical aspects, whereas you were much more focused on the low level situation.
A crux might be that I definitely believe that given an unlimited energy generator, it is very easy to to create a universal computer out of it, and I think energy is much, much closer to a universal currency than you do.