[srssays]

> You can obviously re-write a Python 2 program to be a Python 3 program, so both of those languages are Turing complete.

This is true, but the converse isn't true. e.g. Python and brainfuck are both turing complete, but Python has interfaces around a hell of a lot more syscalls than Brainfuck which only has operations for reading and writing from stdio. You can't write a Python implementation in brainfuck, it is impossible.

[thehardsphere]

No, that's just more work, because you have to write the required syscall interfaces for Brainfuck. There's nothing about Brainfuck that makes that impossible.

There's a difference between "impossible" and "really difficult giant waste of time" here when it comes to discussing Turing completeness.

[vurpo]

Actually, how would you do a syscall in Brainfuck? Its only way to interact with the outside world is through "input byte" and "output byte", and that does not give you the ability to do arbitrary syscalls. As far as I can tell, arbitrary syscalls are impossible to do in Brainfuck (which is why that one person made a fork of Brainfuck with added syscall support).

Of course, syscalls are not related to Turing-completeness in any way. Turing-completeness means that the language can express any computation which is possible to do on a Turing machine. Turing machine computations can not have any side effects, and syscalls are a kind of side effect. Therefore, having syscalls is not necessary for a language to be Turing-complete.