> We have one more mechanism to store values: the return value of a function! Fortunately, the C spec doesn’t impose a maximum stack depth3, and so we can in principle implement a pushdown automata.
Am I misinterpreting this, or would this mean that the abstract machine is turing complete, if you had an unbounded stack?
The C standard bakes in enough details about pointers such that the amount of memory a C program can access (even on a hypothetical infinite-memory machine) is bounded and statically known. Access to an unbounded amount of memory is necessary (but not sufficient) for Turing completeness. Therefore C is not Turing complete.
The argument is—insofar factually true about C which I cannot judge—sound, and I agree that C is according to this view not without bounds, hence not Turing-complete.
But is that viewpoint acceptable in light of what people commonly think of when discussing Turing-completeness? I think it hardly is. Because if it were, then no actually existing software would have ever passed the test for the simple reason that in the physical world unbounded memory can only exist as an approximation, not as an actuality.
But I contend that programs, like computers, can only exist in the physical world. The author seems to conceptualize only computing hardware to be tied to the physical world whereas computing software exists in a Platonic ethereal world of imagination, and therefore, it is enough to hand-wave the inherent limitations of the hardware away with a 'let's imagine'. However, real software is as physical as hardware. Therefore, if we grant the hardware the privilege of not having to be actually infinite to satisfy Turing, we're bound to grant the same to software—in other words, once you can show that in principle, you can always upfront somehow ensure you don't 'run out of paper tape' (as one actually does in newspaper printing, where paper is 'endless' in this sense) and you can likewise ensure, upfront, that your program will be given access to just enough memory, then that does not, in the common understanding, hamper Turing completeness.
Of course, should it turn out that there's a principled reason why one C program cannot ever access more than—pulling out of thin air—23TB of memory, then that would be some sort of argument, even though in practice there's a limit to when we think of memory as 'limited' in a practical sense.
Coming to think of it, can't one write a C program that, while in itself limited in terms of RAM addressability, can spawn copies of itself? When the processes maintain pointers between parent and child process, that should overcome any limitations on Turing-computability since then the tape / RAM can be accessed across process boundaries.
> We have one more mechanism to store values: the return value of a function! Fortunately, the C spec doesn’t impose a maximum stack depth3, and so we can in principle implement a pushdown automata.
Am I misinterpreting this, or would this mean that the abstract machine is turing complete, if you had an unbounded stack?
I beg to differ:
The C standard bakes in enough details about pointers such that the amount of memory a C program can access (even on a hypothetical infinite-memory machine) is bounded and statically known. Access to an unbounded amount of memory is necessary (but not sufficient) for Turing completeness. Therefore C is not Turing complete.
The argument is—insofar factually true about C which I cannot judge—sound, and I agree that C is according to this view not without bounds, hence not Turing-complete.
But is that viewpoint acceptable in light of what people commonly think of when discussing Turing-completeness? I think it hardly is. Because if it were, then no actually existing software would have ever passed the test for the simple reason that in the physical world unbounded memory can only exist as an approximation, not as an actuality.
But I contend that programs, like computers, can only exist in the physical world. The author seems to conceptualize only computing hardware to be tied to the physical world whereas computing software exists in a Platonic ethereal world of imagination, and therefore, it is enough to hand-wave the inherent limitations of the hardware away with a 'let's imagine'. However, real software is as physical as hardware. Therefore, if we grant the hardware the privilege of not having to be actually infinite to satisfy Turing, we're bound to grant the same to software—in other words, once you can show that in principle, you can always upfront somehow ensure you don't 'run out of paper tape' (as one actually does in newspaper printing, where paper is 'endless' in this sense) and you can likewise ensure, upfront, that your program will be given access to just enough memory, then that does not, in the common understanding, hamper Turing completeness.
Of course, should it turn out that there's a principled reason why one C program cannot ever access more than—pulling out of thin air—23TB of memory, then that would be some sort of argument, even though in practice there's a limit to when we think of memory as 'limited' in a practical sense.
Coming to think of it, can't one write a C program that, while in itself limited in terms of RAM addressability, can spawn copies of itself? When the processes maintain pointers between parent and child process, that should overcome any limitations on Turing-computability since then the tape / RAM can be accessed across process boundaries.
In other words: "How many angels can dance on the head of a pin?"
These kinds of pedantic arguments serve nothing but ego.
You said it so much better than I did