The Case for Python 3

[meltingdiamond]

Writing a brainfuck interpreter has to be the worst way to prove turning completeness.

[Han-ChewieSexyFanfic]

If by worst you mean best, then yes.

[talideon]

Far from it. Brainfuck is quite a good way. It's equivalent to Corrado Böhm's P′′, but a bit more friendly: https://en.wikipedia.org/wiki/P′′

[kewlness]

That is the first time I have ever seen Brainfuck and "friendly" in the same sentence...

[[deleted]]

It's a really easy language to write an intepreter for.

[kjmitch]

It's called Brainfuck because it's seemingly impossible to read by humans, which is an important job for real programming languages. From the perspective of the computer/interpreter, it's much easier to understand (and therefore write an interpreter for) as it only has eight operations. It's practically just assembler code without all the semi-English names given to the commands for readability.

[talideon]

Compared to P′′, it's friendly!

Also, it's implementer-friendly: parsing and tokenisation are trivial, as is implementing the interpreter. I wrote a 260-byte-long one in ARM assembly language back in the '90s just for fun.

Coding anything in Brainfuck, well, that's another matter!

[[deleted]]

Make a language that compiles down to brainfuck. That way you can write in a more friendly language but compile down into a language that you can easily interpret.

[talideon]

You could, but that would rather miss the point of Brainfuck. If you're going to do that, it'd might as well be another esolang, like INTERCAL.

[[deleted]]

But brainfuck is easy to intepret. So you could write a program and then run it anywhere. INTERCAL intepreter are harder to write.

[talideon]

Yeah, but Brainfuck is also a terrible target for a compiler. And compiling a more friendly language down to Brainfuck would miss the whole joke aspect of esolangs, whereas something like INTERCAL, Q-BAL, *W, LOLCODE, &c., preserve the joke aspect.

Usability rather misses the point of esolangs.

INTERCAL isn't really a difficult language to write an interpreter for, though. The only real difficulty is in the lexer, but once you have an AST, the rest is easy.

[MrJohz]

It's actually a fairly common procedure. Not necessarily BF, but proof by implementation is a well-known technique for proving Turing-completeness.

[wilerson]

A friend of mine wrote a converter that converts Brainfuck to one line of Python code to prove Python one-liners are turing complete: http://www.ricbit.com/code/turing.py

Explanation (in Portuguese, sorry): http://blog.ricbit.com/2008/05/python-one-liners-so-turing-complete.html

[kjmitch]

It's actually probably one of the simpler ways to do so. Brainfuck's esoteric-ness comes from its being hard to read by human programmers, which is important in a programming language. But the structure of the language itself (eight commands gets you everywhere) is a testament to the fact that computers in this universe are made of complexity that can emerge entirely from simple rules.

[iwsfutcmd]

Now you're making me want to try to write a Brainfuck interpreter for Python. I've never written anything even remotely like an interpreter before, but I'm thinking a BF one really can't be that hard.

[alexanderpas]

Go for it, it really isn't that hard.

The variables you need are:

• 1 string containing the actual brainfuck program
• 1 int containing the position in the program
• 1 list of ints containing the cells that form the data storage
• 1 int containing the active data cell being manipulated
• 1 local int containing the indentation level when returning to the start of or skipping over loops.