Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

BrainFuck is quite far removed from a Turing Machine.

In BrainFuck, the "data" (the memory cells being mutated by the program) are completely separate from the code. As a consequence, BrainFuck code cannot self-modify and it has to maintain two pointers (instruction pointer and memory pointer). BrainFuck also allows the instruction pointer to jump arbitrarily far (i.e. from a "]" back to the corresponding "[").

In constrast, a Turing Machine makes no separation between code and data; it just has a tape (the machine's transition table is more like a language's interpreter than a program). Not only can a program modify itself, for many tasks it must; since the tape only advances one cell at a time, moving between two arbitrary cells requires the contribution of all those in between; whenever we traverse a cell, we must also modify it in preparation for any subsequent traversal.

Whilst BrainFuck is certainly a nice idea, I don't think it's the best example of anything in particular.

I wrote up some thoughts on this a few years ago http://chriswarbo.net/blog/2014-12-22-minimal_languages.html



> In constrast, a Turing Machine makes no separation between code and data; it just has a tape (the machine's transition table is more like a language's interpreter than a program).

I think you're conflating "Turing machine" with "universal Turing machine".

In a standard Turing machine, the state transition table is the "code". That code could be an interpreter for another language, including for arbitrary Turing machines, or it could be something entirely different. Either way, it's static, just like a Brainfuck program. In fact, the translation from Brainfuck to a Turing machine is trivial: if each cell of the tape is a byte, then each character of the program becomes one state of the machine.




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: