I'm trying to write a bit of code in Brainfuck, but I stumbled into some problems.That got me wondering how Brainfuck is Turing complete, as I understand it Turing complete means a language or machine can calculate any function.What got me wondering how, is that I have not been able to find or come up with a way of finding the sign of a number. Because the signum function is a function, and a Turing complete machine can calculate all functions, how can Brainfuck be Turing complete?The answer I'm looking for is either an explanation why my statement is true or untrue or an algorithm that can calculate the sign of a number.
How is brainfuck turing complete
turing completeness;brainfuck
Assuming Brainfuck's memory cells have minimum and maximum values*, just put the number in two cells, then keep incrementing one and keep decrementing the other until one of them hits zero. There's your sign algorithm.Now for the general question. A Turing complete machine can calculate all functions isn't a great definition to start with because function is too vague. That would allow you to argue that Brainfuck is not Turing complete because it's impossible to write web servers and web browsers in it, or that C++03 is not Turing complete because it's impossible to write multi-threaded programs in it (without non-standard extensions).Learning how to formally prove Turing completeness is something best learned from a textbook on the theory of computation. But there are many useful heuristics you can use in practice, such as:Conditional branching is possible in any Turing-complete language.Loops that execute for infinitely many iterations or arbitrarily many finite iterations are possible in any Turing-complete language.Any Turing-complete language can be used to write a program that requires infinte memory or an arbitrarily large amount of memory. All Turing-complete languages support at least some kind of input and output for their programs.The halting problem is unsolvable for any Turing-complete language. In other words, it's impossible to write a program that can look at other programs and tell with certainty whether or not they're capable of going into an infinite loop.Brainfuck meets all of these criteria. Most Brainfuck implementations arguably fail the memory criteria, but that argument applies to all programming languages since in the real world computers always have finite memory.*Technically, the unofficial Brainfuck standard does allow for a bignum implementation, and I'm also ignoring the possibility of inputting a number that doesn't fit in one memory cell for a non-bignum implementation. But I decided not to nerd-snipe myself with those problems for right now; I'm pretty sure they can be solved if we really wanted to.