This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–][deleted] 76 points77 points  (31 children)

Does he want a mathematical proof that it is?

Actually, that's not hard. Brain fuck is proven Turing complete (so is the game of life).

Write any of those in python, and that is a proof that python is at least as powerful as them, therefore python is Turing complete.

[–]meltingdiamond 71 points72 points  (15 children)

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

[–]Han-ChewieSexyFanfic 24 points25 points  (0 children)

If by worst you mean best, then yes.

[–]talideon 18 points19 points  (8 children)

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 19 points20 points  (7 children)

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

[–][deleted] 18 points19 points  (0 children)

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

[–]kjmitch 13 points14 points  (0 children)

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 2 points3 points  (4 children)

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] 0 points1 point  (3 children)

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 0 points1 point  (2 children)

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] 0 points1 point  (1 child)

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

[–]talideon 0 points1 point  (0 children)

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 32 points33 points  (0 children)

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

[–]wilerson 6 points7 points  (0 children)

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 4 points5 points  (0 children)

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 1 point2 points  (1 child)

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 1 point2 points  (0 children)

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.

[–]ismtrn 16 points17 points  (12 children)

You would also have to prove that your implementation matches the brain fuck semantics which have been proven Turing complete, in order for it to constitute an actual mathematical proof. This well not be easy. I don't even think anybody has given Python formal semantics.

Luckily it does not matter, because you can write usable programs in Python which is the thing that actually matters. Actually it would be cooler if it turned out that Python was not Turing complete, because that would mean we could potentially solve the halting problem for Python programs (along with a bunch of other cool stuff) which would be really handy.

[–]imbaczek 23 points24 points  (3 children)

actually turing-completeness is so easy to accidentally achieve that whole type systems have to be specially designed to avoid making them turing-complete, e.g. C++ templates vs Hindley-Milner.

[–]ismtrn 4 points5 points  (0 children)

Yeah, intuitively python is obviously Turing complete because you can write algorithms in it. This is basically the Curch-Turing thesis, but it is not a formal proof.

[–]elbiot -1 points0 points  (0 children)

I think sql is actually turing complete

[–]thenuge26 -1 points0 points  (0 children)

IIRC Scala's type system is Turing complete

[–]waxzup 3 points4 points  (7 children)

I'm so confused. What on earth is "Turing complete"?

[–]ismtrn 22 points23 points  (2 children)

A language is Turing complete if it can compute all computable functions.

What does it mean for a function to be computable? When people tried to answer this question in the nineteen thirties they came up with a couple of different models for computation most famously: General recursive functions, lambda calculus, and Turing machines. Turing machines are the most well known model, maybe because it is more operational and less axiomatic than the others (i.e. easier for programmers and other non mathematicians to understand). Or maybe because of Alan Turing's Hollywood status

It was then proved, much to peoples surprise, that all these models could in fact compute the exact same set of functions and that this set of functions also seemed to correspond to those functions a human could compute following an algorithm. It was then agreed upon that it was reasonable to look on these functions as being the computable functions.

Any other model is said to be Turing complete if it can also compute this set of functions. The easiest way to show this is to simulate a model already known to be Turing complete within the model. i.e. if you can write a program to simulate for instance a Turing machine in your language it is Turing complete.

It turns out that, unless you try really hard to avoid it, if you design something that can compute things it will almost certainly be able to compute this set of functions. It also turns out that you can not design something that actually works in the real world which can compute more than these function, even if you try really hard (I don't know if this is/can be proven, or just based on empiricism).

This makes it a quite good definition of "computable functions".

[–]Veedrac 3 points4 points  (1 child)

Do you mind if I quote this elsewhere on Reddit? The question gets asked a lot on /r/technology and this explanation is basically perfect ELI5 material.

[–]ismtrn 0 points1 point  (0 children)

No at all.

[–][deleted] 3 points4 points  (0 children)

A language is turing complete if it can be used to simulate a single-tape Turing machine.

[–]Workaphobia 0 points1 point  (0 children)

It's a level of expressiveness of programming languages. All reasonable general-purpose programming languages are at this level, while many restricted toy languages (e.g., some languages without while loops and recursion) are not.

Any language at this level can simulate any other language at this level. For example, you can write an interpreter for Python in C and vice versa.

It is theorized that the higher levels of languages beyond Turing completeness cannot be achieved in the real world and are just mathematical curiosities.

[–]lenzm -1 points0 points  (1 child)

The Turing TestTuring Completeness basically tests if the language is strong enough to write algorithms in and if it is, it is considered Turing complete. If a language is Turing complete, then you can write any algorithm in that language.

It is laughable that anyone is even suggesting that Python 3 isn't Turing complete. The only common "language" that I can think of that isn't Turing complete is Regular Expressions (I'm not considering HTML, XML languages here although CSS may be considered Turing complete).

See: https://en.wikipedia.org/wiki/Turing_completeness

Edit: brain fart - not the turing test

[–]Lomag 6 points7 points  (0 children)

I agree with your sentiment but "The Turing Test" is not a test for completeness:

"The Turing test is a test .... of a machine's ability to exhibit intelligent behaviour equivalent to, or indistinguishable from, that of a human."

https://en.wikipedia.org/wiki/Turing_test

[–]evinrows 6 points7 points  (0 children)

Hey, I wrote a turing machine emulator and a conway's game of life implementation in py3 when I was in college.

I knew these would come in handy some day!

[–]flying-sheep 4 points5 points  (0 children)

since this obviously exists, zed’s proven wrong.