Re:Brainfuck interpreter written in the C preprocessor
by evincarofautumn on Friday November 16, 2012 @07:33PM
(#4796603)
The C preprocessor is a pushdown automaton, which if you add fixpoints (unbounded recursion) becomes a bounded storage machine. Our actual computers are such machines, which if you give them an infinite amount of memory are Turing machines. A language can be Turing-complete even if the implementation of that language is not.
[ Parent
| on HN ]
Re:Brainfuck interpreter written in the C preprocessor
by tjgq on Saturday November 17, 2012 @01:43PM
(#4798716)
Interestingly, any physical, finite machine can be modelled as a finite state automaton (which is even more limited than a pushdown automaton) with a large enough state space. The distinction only comes up when you consider idealized infinite machines.
Theory of computation is weird.
Re:Brainfuck interpreter written in the C preprocessor
by mistercow on Friday November 16, 2012 @07:47PM
(#4796649)
Can C be implemented such that pointers do not have a fixed size? That is to say, suppose you have a hypothetical machine that uses bignum memory addresses. Can C be implemented to run on that machine without cheating and using a fixed pointer size?
Re:Brainfuck interpreter written in the C preprocessor
by scott_s on Friday November 16, 2012 @07:55PM
(#4796669)
You don't need to reason about C's pointers to consider its Turing Complete. That it allows arbitrary storage, it has conditionals and allows full looping (either unbounded loops or full recursion) is enough. That is, a language that had C's semantics sans pointers would still be Turing Complete.
Re:Brainfuck interpreter written in the C preprocessor
by mistercow on Saturday November 17, 2012 @01:06AM
(#4797379)
Are you saying that C with neither pointers nor arrays would still be Turing complete? I am skeptical.
Re:Brainfuck interpreter written in the C preprocessor
by knz42 on Sunday November 18, 2012 @09:30AM
(#4800623)
It's not, and it's not obvious.
https://tdotc.wordpress.com/2012/11/18/on-the-turing-complet...
Re:Brainfuck interpreter written in the C preprocessor
by scott_s on Sunday November 18, 2012 @11:12AM
(#4800807)
I actually pondered on this for a long time, and I haven't come to a conclusion. I cannot, however, counter any of your arguments, as I thought some of the same things myself.
This is a surprising train of thought.