4 ms·

as all programming comes down to pointer twiddling, either under or over the hood, is any language turing complete?

• tromp 2y ago
  Sure; one of the simplest languages possible, the binary lambda calculus [1] is Turing complete. It has no pointers, no variables, and no data type sizes. Only functions (from functions to functions). Everything else must be built out of functions. Brainfuck with an unbounded tape length is similarly Turing complete. I think less esoteric languages like Haskell and Scheme qualify too. [1] https://www.ioccc.org/2012/tromp/hint.html https://www.ioccc.org/2012/tromp/hint.html
  • zabzonk 2y ago
    but under the hood (the implementation of an actual programming language) it is all pointers - not?
    • tromp 2y ago
      The article admits that real machines have bounded memory, the argument is about language specifications only.