Menu
Is Brainfuck Turing-complete if the cells are bits, and the + and - operations simply flip a bit? Is there a simple proof that Brainfuck-like languages are Turing-complete regardless of the cell size, or do I need to think of a program that simulates a Turing machine? How would I know if there isn't one?
EDIT: I found an answer to my question: Brainfuck with bit cells is called Boolfuck. Ordinary Brainfuck can be reduced to it, so Boolfuck is Turing-complete.
740
A system can only be considered to be Turing complete if it can do anything a universal Turing machine can. Since the universal Turing machine is said to be able to solve any computable function given time, Turing complete systems can, by extension, also do so.
In colloquial usage, the terms "Turing-complete" and "Turing-equivalent" are used to mean that any real-world general-purpose computer or computer language can approximately simulate the computational aspects of any other real-world general-purpose computer or computer language.
What Does Turing Complete Mean? A system is said to be "Turing complete" in computer theory if it can be used to emulate a Turing machine, which is a theoretical construct designed by mid-century mathematician and computer scientist Alan Turing.
A programming language is Turing complete if it can compute all functions that a Turing machine can compute. Amongst other things, this means it can decide any decidable set.
This answer should suit you well; it has a very specific definition of what features make a language turing complete.
Here's the gist of it:
In general, for an imperative language to be Turing-complete, it needs:
A form of conditional repetition or conditional jump (e.g.,
while,if+goto)A way to read and write some form of storage (e.g., variables, tape)
105
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
