10

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.

Improve this question
11
  • 10
    "I have not been able to do X" != "X is impossible" esolangs.org/wiki/Brainfuck_algorithms#z_.3D_sign.28x-y.29
    – Philip Kendall
    Apr 16, 2016 at 15:43
  • 1
    "The signs of the two numbers must be known." The sign of both numbers must be known to be able to find the sign of one. How does that make the sign computable?
    – S.Klumpers
    Apr 16, 2016 at 15:47
  • 1
    OK, so that specific example doesn't work. But the general point still stands - you not being able to do something proves nothing at all.
    – Philip Kendall
    Apr 16, 2016 at 15:49
  • 5
    "Turing complete means a language or machine can calculate any function." – That is very much not what it means. In fact, there are infinitely many functions that no Turing-complete language/machine can compute. The most famous function that is impossible to compute is the Halting Function H(p) = 1 if p halts, 0 otherwise.
    – Jörg W Mittag
    Apr 16, 2016 at 16:38
  • 1
    Right @JörgWMittag, but my computer can calculate the sign function and my computer is a Turing-complete machine, therefore the sign function is a Turing-computable function, so anything that can't calculate the sign function is not a Turing-complete machine. Is that right?
    – S.Klumpers
    Apr 16, 2016 at 16:53

2 Answers 2

Reset to default
17

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.

Improve this answer
5
  • 1
    Exactly why is it impossible to write web servers/browsers in brainfuck?
    – candied_orange
    Apr 16, 2016 at 23:09
  • Because it removes the possibility to interface directly with your hardware, including your wifi chip or ethernet adapter.
    – S.Klumpers
    Apr 17, 2016 at 5:47
  • 1
    Input/output in the language itself isn't strictly necessary to be turing-complete; Brainfuck can still compute any computable function with the only input being storing numbers in the memory cells before it starts and the only output being to read the contents of the memory after it halts.
    – faubi
    May 19, 2016 at 12:47
  • 1
    Isn't it always the case that a language cannot necessarily have I/O? it has to be included "extra". it's always going to be up to the existence of underlying hardware and O/S and having functions that access them as to whether or not you can have I/O. It's not really an issue of the language. (I suppose maybe the issue with BF is the limited instruction set that doesn't leave any room for adding anything else, but it can still be extended.)
    – Dave Cousineau
    Nov 21, 2017 at 2:52
  • The halting problem part looks the hardest to prove. Can you explain further?
    – SOFe
    May 6, 2019 at 16:20
-2

Faubi is right regarding the input/output of BF programs.

Regarding the halting problem, however... Suppose there were a BF program to tell if a program halts when given itself as an input. Then suppose that algorithm says the BF program will halt when given itself as input.

Well, then a slightly changed BF program can loop forever (if told that it halts), or halt (if told that it doesn't halt). This is a contradiction so the premise is false. QED.

Does that make sense?

Improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.