3 ms·

By this logic, there aren’t any existing Turing-complete language implementations, since memory is always finite. This doesn’t seem like a helpful argument.

by KMnO4 2y ago

DSMan195276 2y ago
The question isn't about a C implementation but about the language standard itself, which defines C in terms of an abstract machine. There are definitely some languages that are turing complete when considered in this regard.
mort96 2y ago
It doesn't have to be "helpful" to be correct. If, say, my laptop, with its 16GiB of RAM (meaning finite number of possible states), was actually Turing complete, that would have profound implications for mathematics. That would mean that there was an upper bound for the memory required for computation. But that's obviously not the case, because my laptop isn't Turing complete. Does this affect your daily life as a programmer? Well, no. But does the distinction between "Turing machine" and "Turing-machine-like system but with finite memory" matter? In some contexts, yes. There are people whose profession it is to think about computation with more rigour than us programmers. (FWIW, in most languages, while implementations aren't Turing complete, the language spec is. C is the odd one out by requiring implementations to impose an upper bound on the amount of memory which can be addressed.)
- rtb 2y ago
  You are technically correct, but this is still a pointless argument to make. It's pretty easy to see that any finite machine isn't Turing Complete, because you just ask whether it can compute a function that doesn't fit in its memory. So, for your laptop: define a function that's true on some number larger than would fit in 16GiB (fiddling the definitions as necessary depending on exactly how you define input / output etc.) As wikipedia says: > No physical system can have infinite memory, but if the limitation of finite memory is ignored, most programming languages are otherwise Turing-complete. The convention is to ignore the infinite case, when talking about real systems because a) most things we want answers to are not large enough for this to make a difference and b) otherwise no real system is Turing-complete, and that's not a helpful definition.
  - mort96 2y ago
    This isn't about physical systems. It's about programming language specs. Most programming languages are Turing complete as specified. C isn't. That's interesting.

By this logic, there aren’t any existing Turing-complete language implementations, since memory is always finite. This doesn’t seem like a helpful argument.

by KMnO4 2y ago

By this logic, there aren’t any existing Turing-complete language implementations, since memory is always finite. This doesn’t seem like a helpful argument.

DSMan195276 2y ago

The question isn't about a C implementation but about the language standard itself, which defines C in terms of an abstract machine. There are definitely some languages that are turing complete when considered in this regard.

mort96 2y ago

It doesn't have to be "helpful" to be correct. If, say, my laptop, with its 16GiB of RAM (meaning finite number of possible states), was actually Turing complete, that would have profound implications for mathematics. That would mean that there was an upper bound for the memory required for computation. But that's obviously not the case, because my laptop isn't Turing complete. Does this affect your daily life as a programmer? Well, no. But does the distinction between "Turing machine" and "Turing-machine-like system but with finite memory" matter? In some contexts, yes. There are people whose profession it is to think about computation with more rigour than us programmers. (FWIW, in most languages, while implementations aren't Turing complete, the language spec is. C is the odd one out by requiring implementations to impose an upper bound on the amount of memory which can be addressed.)

rtb 2y ago
You are technically correct, but this is still a pointless argument to make. It's pretty easy to see that any finite machine isn't Turing Complete, because you just ask whether it can compute a function that doesn't fit in its memory. So, for your laptop: define a function that's true on some number larger than would fit in 16GiB (fiddling the definitions as necessary depending on exactly how you define input / output etc.) As wikipedia says: > No physical system can have infinite memory, but if the limitation of finite memory is ignored, most programming languages are otherwise Turing-complete. The convention is to ignore the infinite case, when talking about real systems because a) most things we want answers to are not large enough for this to make a difference and b) otherwise no real system is Turing-complete, and that's not a helpful definition.
- mort96 2y ago
  This isn't about physical systems. It's about programming language specs. Most programming languages are Turing complete as specified. C isn't. That's interesting.