Hacker News new | ask | show | jobs
by bidirectional 1820 days ago
You can't actually implement everything in Brainfuck. You can implement something which is performing an equivalent computation in an abstract, mathematical sense. But there's no way to write Firefox or Windows or Fortnite in Brainfuck. Turing completeness means you can evaluate any computable function of type N -> N (and the many things isomorphic to that), it doesn't give you anything else.
2 comments

Just as a Turing machine requires an infinitely sized tape to compute any computable function, so too would brainfuck require an indirect sized tape (or whatever it’s called in BF) to compute any computable function. Since memory is finite, neither of these properties are actually available on real hardware.
I am interested in computation. Period. Not any particular model of computation (programming language); and not merely computation with functions from N->N.

Quoting from "http://math.andrej.com/2006/03/27/sometimes-all-functions-ar..."

"The lesson is for those “experts” who “know” that all reasonable models of computation are equivalent to Turing machines. This is true if one looks just at functions from N to N. However, at higher types, questions of representation become important, and it does matter which model of computation is used."