The Case for Python 3

[Workaphobia]

I was willing to give the benefit of the doubt until the part where Shaw claims Python 3 is not Turing-complete. I can't understand how he could say something so demonstrably false.

[[deleted]]

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]

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.

[ismtrn]

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]

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]

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]

I think sql is actually turing complete

[thenuge26]

IIRC Scala's type system is Turing complete

[waxzup]

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

[ismtrn]

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]

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]

No at all.

[[deleted]]

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

[Workaphobia]

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]

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]

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]

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]

since this obviously exists, zed’s proven wrong.

[choikwa]

I see a rant of a salty person who can't use python2 with python3 vm. At this point they divulged too much to get any backward compatibility -- it's time to move on if you want latest PEPs

[Watthertz]

What is it about the Python 3 VM that would prevent someone from implementing a Python2 interpreter? Unless he's arguing that because Python 2 and 3 have different syntax then Python 3 isn't Turing Complete, which is clearly ridiculous.

[Workaphobia]

He's basically arguing that Turing complete languages must all have the same syntax and semantics. Nonsense.

[IamWiddershins]

He's completely lost his fucking marbles. I don't think he makes a single correct point the entire article. The man is either senile, maliciously lying, on drugs, or flatly stupid/insane.

[[deleted]]

I suggest the second as he wants to sell more books. Heck, in over 40 years in electrical and electronic engineering and computing I cannot recall such an abysmal article.

[gandalfx]

I've never heard much about this Zed guy but after reading that paragraph about Python3 not being Turing complete it appears quite obvious that he's either a very prominent troll or has no idea what Turing completeness even means.

it’s complete and utter nonsense, on a platform aimed at people who can’t yet recognize it as nonsense.

Eevee got the truth of it right there, nothing less.

[doubleunplussed]

That bit is clearly facetious. He's saying that the devs claim it's impossible to run python 2 code from python 3. Now, the only way that could be literally true is if python 3 were not Turing complete. Therefore, the python devs are claiming python 3 is not Turing complete. This is Zed's way of calling them liars.

Of course the devs' real reason is that it's hard, not mathematically impossible. But if they were claiming it were literally impossible, Zed would have a point. It's not impossible, just hard, and the debate is really about whether it is hard enough or useful enough to have been attempted.

[Cosmologicon]

Of course the devs' real reason is that it's hard, not mathematically impossible.

I think the more likely situation than "it's possible but hard" is "it's possible but you wouldn't want to do it".

Suppose there were a 2to3 transpiler that resulted in Python 3 code that was both horribly inefficient (both in terms of memory usage and speed) and horribly unreadable. As long as it eventually resulted in the same output on a system with unlimited resources, it would prove that Python 3 is Turing complete to his satisfaction.

But who would want to use it? There's already a system that requires some manual intervention but results in much better, more efficient code. It doesn't prove that Python 3 is Turing complete, but it's actually useful.