3 ms·

How is it that any computational device in physical reality is turing complete, since it must fit in our universe which can hold finite information? Doesn't tha

How is it that any computational device in physical reality is turing complete, since it must fit in our universe which can hold finite information? Doesn't that basically render the practical definition useless?

olliej 2y ago
I think the post is just a pedant/gotcha argument that is correct only in the “technically correct” sense, but is otherwise useless, as the same argument applies to literally any “Turing complete” system.
- mort96 2y ago
  > the same argument applies to literally any “Turing complete” system. Only physical "Turing complete" systems. JavaScript, as specified by ECMA, is properly Turing machine; you can express a program which will allocate an arbitrary amount of objects. In the "JavaScript abstract machine", there is no upper limit. In C, there is necessarily a finite upper limit to the amount of objects allocated, since every object needs a unique address and addresses are represented by finite-bit pointers. That means that the "C abstract machine" as defined by ISO can not even in principle allocate arbitrarily many objects. (And yes, this all means that any Turing-machine-like systems built in the real world aren't proper Turing machines, since strictly speaking, a Turing machine is a theoretically construct with an infinitely long tape.)
mort96 2y ago
Their tl;dr isn't quite right. Any physical computing system has finite capacity, so you're right, no physical computing system is actually Turing complete. However, in most languages (JavaScript, Python, Java, ...) there's no concept of an object's location in memory as expressed by a finite number of bits. In those languages, you can express programs which will create an ever increasing number of objects. Trying to run that program will eventually cause a crash as you run out of space, but the source code itself encodes a program which would allocate objects with no upper bound. That's not the case for C. In C, every object has a unique address. That address is encoded in a fixed number of bits. As such, you can't even write source code which allocates objects with no upper bound; the upper bound will always be 2 to the power of the number of bits in a pointer.

olliej 2y ago

I think the post is just a pedant/gotcha argument that is correct only in the “technically correct” sense, but is otherwise useless, as the same argument applies to literally any “Turing complete” system.

mort96 2y ago
> the same argument applies to literally any “Turing complete” system. Only physical "Turing complete" systems. JavaScript, as specified by ECMA, is properly Turing machine; you can express a program which will allocate an arbitrary amount of objects. In the "JavaScript abstract machine", there is no upper limit. In C, there is necessarily a finite upper limit to the amount of objects allocated, since every object needs a unique address and addresses are represented by finite-bit pointers. That means that the "C abstract machine" as defined by ISO can not even in principle allocate arbitrarily many objects. (And yes, this all means that any Turing-machine-like systems built in the real world aren't proper Turing machines, since strictly speaking, a Turing machine is a theoretically construct with an infinitely long tape.)

mort96 2y ago

Their tl;dr isn't quite right. Any physical computing system has finite capacity, so you're right, no physical computing system is actually Turing complete. However, in most languages (JavaScript, Python, Java, ...) there's no concept of an object's location in memory as expressed by a finite number of bits. In those languages, you can express programs which will create an ever increasing number of objects. Trying to run that program will eventually cause a crash as you run out of space, but the source code itself encodes a program which would allocate objects with no upper bound. That's not the case for C. In C, every object has a unique address. That address is encoded in a fixed number of bits. As such, you can't even write source code which allocates objects with no upper bound; the upper bound will always be 2 to the power of the number of bits in a pointer.