3 ms·
If you want to talk about this kind of technicality, here are three other avenues through which I believe Turing completeness of C can be achieved: 1. As https
by GabrielTFS 4y ago
If you want to talk about this kind of technicality, here are three other avenues through which I believe Turing completeness of C can be achieved:
1. As https://www.open-std.org/jtc1/sc22/wg14/www/docs/dr_260.htm https://www.open-std.org/jtc1/sc22/wg14/www/docs/dr_260.htm helpfully points out, "If two objects have identical bit-pattern representations and their types are the same they may still compare as unequal", and "[implementations] may also treat pointers based on different origins as distinct even though they are bitwise identical". It can thus be argued that, with a rather strict definition of provenance (i.e. how pointer values may be constructed), one could construct an implementation where every byte of every pointer is tagged with additional unbounded data that lets the whole pointer be properly dereferenced (I say every byte so that you're able to convert the pointer to an integer and convert it back to the same valid pointer), and where, as allowed by DR 260, pointers that have identical observable bit-pattern representations might not compare equal if they point to different objects. Thus, that implementation could create an unbounded amount of pointers.
2. Spawning off another thread and using infinite recursion (C has no defined recursion depth limit, and if you want to argue about automatic variables needing addresses or whatever and that the as-if rule doesn't cover that, there's `register` which makes address-less variables) to have two pushdown automatas that can together work as a Turing Machine.
3. Using variadic arguments. With `va_copy`, one can iterate through variadic arguments multiple times, and thus `va_list` can be used to implement a mechanism equivalent to pointers without actual pointers (any sane implementation probably uses a pointer for `va_list` somewhere in it, but that's not a problem here) and thus make a pushdown automata with 2 stacks
- camel-cdr 4y agoLet me address 2. and 3. first, because 1. is probably correct. 2. The problem with that is that you may have infinite recursion, but you can only pass finite amounts of memory between recursion steps. This has also been addressed by https://cs.stackexchange.com/a/60978 https://cs.stackexchange.com/a/60978. 3. I don't follow, how could you create a growing `va_list`? Edit: Actually, I think I do now, so you essentially create a sort of linked list of `va_list`s? 1. This is probably correct. You'd need to be able to round trip through a void*, but that could still be implemented to retain the tagged data. I thought of pointer tagging more in terms of marking addresses with certain memory protection properties, but what you suggest should be possible. There may still be some wording disallowing it, but I couldn't find it.
- GabrielTFS 4y ago> 2. The problem with that is that you may have infinite recursion, but you can only pass finite amounts of memory between recursion steps. This has also been addressed by https://cs.stackexchange.com/a/60978 https://cs.stackexchange.com/a/60978. If I have two stacks (by spawning another thread), don't I have two PDAs ? That's what that stackoverflow post indicates, and IIRC two PDAs are equivalent to a Turing machine.