3 ms·

I'd say the interpreter is interpreting a non-Turing complete subset of the bignum language. That said, what is and isn't "Turing complete" is hardly relevant f

by aji 11y ago

I'd say the interpreter is interpreting a non-Turing complete subset of the bignum language. That said, what is and isn't "Turing complete" is hardly relevant for practical purposes. C has obviously been very useful as a language, despite whatever theoretical statements can be proven about it.

mannykannot 11y ago
It is not clear to me why it would be a subset (I'm assuming proper subset here) or why it would have to be non- Turing-complete. I agree that none of this has any obvious relevance to the practical usefulness of C, but all of us here in this thread have chosen to put that aside, at least for now, in order to contemplate a somewhat esoteric though less practical question.
- aji 11y ago
  The key distinction to note is the one between specifications and implementations. As a small example, consider Brainfuck. The Brainfuck specification (if such a thing exists) has no upper bound on the number of memory cells, but practical implementations generally do have a limit that "useful" Brainfuck programs will rarely hit. The specification describes a TC language, while the implementation does not. Therefore, if a language is TC according to its specification, but has an implementation in a language that is shown to not be TC, then it follows that the implementation must be of a non-TC subset of the language. This is, of course, assuming both that the specification has been proven TC, and that the implementing language has been proven non-TC. I believe the point being made in the paper is that the C specification itself is restrictive enough that it describes a non-TC language. In other words, any implementation of C that is truly Turing complete would be violating the specification in some way. In that case, it follows that a C implementation of a TC language (such as the bignum language) must only be an implementation of a non-TC subset of the language. (As an aside, consider that nothing running on an isolated machine will ever be truly TC, since an isolated machine has a finite amount of memory and so can't be TC. It's not that much of an inferential jump to see that this kind of TC-breaking limitation could end up in the specification of C, a language quite close to the metal.)

by aji 11y ago

mannykannot 11y ago

It is not clear to me why it would be a subset (I'm assuming proper subset here) or why it would have to be non- Turing-complete. I agree that none of this has any obvious relevance to the practical usefulness of C, but all of us here in this thread have chosen to put that aside, at least for now, in order to contemplate a somewhat esoteric though less practical question.

aji 11y ago
The key distinction to note is the one between specifications and implementations. As a small example, consider Brainfuck. The Brainfuck specification (if such a thing exists) has no upper bound on the number of memory cells, but practical implementations generally do have a limit that "useful" Brainfuck programs will rarely hit. The specification describes a TC language, while the implementation does not. Therefore, if a language is TC according to its specification, but has an implementation in a language that is shown to not be TC, then it follows that the implementation must be of a non-TC subset of the language. This is, of course, assuming both that the specification has been proven TC, and that the implementing language has been proven non-TC. I believe the point being made in the paper is that the C specification itself is restrictive enough that it describes a non-TC language. In other words, any implementation of C that is truly Turing complete would be violating the specification in some way. In that case, it follows that a C implementation of a TC language (such as the bignum language) must only be an implementation of a non-TC subset of the language. (As an aside, consider that nothing running on an isolated machine will ever be truly TC, since an isolated machine has a finite amount of memory and so can't be TC. It's not that much of an inferential jump to see that this kind of TC-breaking limitation could end up in the specification of C, a language quite close to the metal.)