+ 4

Why "Brainfuck" is a Turing-Complete Language?

That language has less syntaxes than, other languages. But, why it is Turning-Complete?

23rd Jan 2018, 9:41 PM
Surajit
Surajit - avatar
2 Réponses
23rd Jan 2018, 9:47 PM
jay
jay - avatar
+ 3
Also remember that a turing machine is just a moving head on a tape. It reads one instruction off the tape and goes either left or right, writing something to the tape at that location. What does brainfuck do? It has a tape, you can move left or right, and you can write something to your current location. So not only can brainfuck model a turing machine, it pretty much is one! Brainfuck exactly implements what is needed to emulate a turing machine and not a single thing more, so we sometimes refer to brainfuck as being in the "turing tar-pit". That's a reference to Alan Turing himself, who once said: "Be aware of the turing tar-pit in which everything is possible but nothing of interest is easy"
23rd Jan 2018, 10:01 PM
Schindlabua
Schindlabua - avatar