Berlin Brown - 8 months ago 83

Brainfuck Question

Does anyone have a set of cellular automata rules for a brainfuck interpreter? I assume it would it be similar to implementations of a universal turing machine. Those exist on wolfram site but I don't know how to tweak them for a BF system.

Answer

Cellular automata are "in-place" rules. A set of rules will not need states before the current one, to calculate the next one.

BF, however, does not calculate "in-place": it has a pointer and a stack, and the program-space itself must not change while evaluating. It is difficult to design a set of cellular automata rules that evaluate a BF program, as the pointer variable and stack space is global state.

BF programs are one dimensional, so in Von Neumann sense the "cellular" automata would be nonsensical.

It is true that there exists cellular automata that are Universal Turing Machines, but that does not mean (per se) that all Universal Turing Machines are cellular automata.

Source (Stackoverflow)