+ 4
Why "Brainfuck" is a Turing-Complete Language?
That language has less syntaxes than, other languages. But, why it is Turning-Complete?
2 odpowiedzi
+ 10
Because it can be used to simulate a Turing machine.
https://en.m.wikipedia.org/wiki/Turing_machine
https://en.m.wikipedia.org/wiki/Turing_completeness
+ 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"