6 ms·

Is there are relationship between the lambda calculus and Brainfuck and other few instruction set languages? Edit: well, an easy find, https://esolangs.org/wi

• c1ccccc1 7y ago
  Also: https://esolangs.org/wiki/Iota https://esolangs.org/wiki/Iota
• posterboy 7y ago
  there's an isomorphism, because bf is np complete, as is simply typed lc. simply speaking, bf can implement lc, and vice versa, which would proof the claim. Edit: the ugly bit is that IO is always an ugly hack and potentially makes the program indetermined and thus impossible to proof a priory. but one can probably prove that they are equivalently unprovable.
  • anchpop 7y ago
    > because bf is np complete, as is simply typed lc. Do you mean turing complete?
• tromp 7y ago
  I wrote a Brainfuck interpreter in (binary) Lambda Calculus [1], which was included in my 2012 IOCC submission [2]. Writing a lambda calculus interpreter in BF would be a fun challenge. [1] https://tromp.github.io/cl/Binary_lambda_calculus.html#Brainfuck https://tromp.github.io/cl/Binary_lambda_calculus.html#Brain... [2] http://www.ioccc.org/2012/tromp/hint.html http://www.ioccc.org/2012/tromp/hint.html