5 ms·

I've said it before and I'll say it again: go and learn Brainfuck. Just write a program that outputs your name or does FizzBuzz or something trivial, that's eno

by exDM69 10y ago

I've said it before and I'll say it again: go and learn Brainfuck. Just write a program that outputs your name or does FizzBuzz or something trivial, that's enough to get a grasp of it. Brainfuck is to Turing machines what Lisp is to Lambda calculus. Minimum viable amount of syntactic sugar (and a bit of "semantic sugar" as well, it's nicer to work in bytes than bits) to make it usable as a programming language. Lambda calculus is just a bit more practical formalism than Turing machines, that's why Lisp is genuinely useful as a programming language, unlike Brainfuck. That doesn't make learning about Turing machines any less useful as a brain teaser exercise.

nickpsecurity 10y ago
I've always thought the Turing LISP was Forth. It's a tiny, stack machine with few ops plus some LISP capabilities. Also implemented in efficient hardware.
- bogomipz 10y ago
  Is Turing Lisp a flavor of LISP? This is the first I've heard of it.
  - nickpsecurity 10y ago
    Turing Machines and Lambda Calculus are equivalent in power, but opposite in style, ways of formally describing computing. Imperative programming came from one and functional programming from the other. One of simplest... conceptually and in implementation... versions of Lambda Calculus is LISP. I'm guessing you already know what it can do. In Turing/Imperative Land, I suggested Forth comes closest to being simplest of very powerful languages. There's probably implementations of all of these in all the others out there. I'm just saying Forth is a Turing-style language with LISP-like simplicity and benefits.
    - bogomipz 10y ago
      Ah OK, thanks for the clarification. That dichotomy makes perfect sense. I haven't really looked at Forth, is your comment about its "LISP-like simplicity" why is such a perennial favorite amongst language aficionados? Any recommended readings on the subject(Forth) ?
      - nickpsecurity 10y ago
        Intro here: https://users.ece.cmu.edu/~koopman/forth/hopl.html https://users.ece.cmu.edu/~koopman/forth/hopl.html Yosefk's write-up is the definitive one for me, though, showing an intro, some amazing stuff about it, weird stuff, and reasons for ultimately not going with it. Link: http://yosefk.com/blog/my-history-with-forth-stack-machines.html http://yosefk.com/blog/my-history-with-forth-stack-machines....
  - grkvlt 10y ago
    No, he means Turing machines are to FORTH as Lambda Calculus is to Lisp.
    - bogomipz 10y ago
      Thanks.
YeGoblynQueenne 10y ago
>> Brainfuck is to Turing machines what Lisp is to Lambda calculus. Indeed, the lambda calculus was never meant as a real programming language.
- joelg 10y ago
  > Indeed, the lambda calculus was never meant as a real programming language. In fact, not even Lisp itself was originally meant as a real programming language! McCarthy invented it as a notation for mathematical proofs, and one of his grad students thought it might make a good language.
  - nickpsecurity 10y ago
    Never knew that. That's a trip. Great accident to have in one's career given all that came of it.
    - AnimalMuppet 10y ago
      http://www.paulgraham.com/icad.html http://www.paulgraham.com/icad.html Look for the section heading "Catching Up with Math".
      - nickpsecurity 10y ago
        That was a good read. Appreciate the link.
  - chriswarbo 10y ago
    In hindsight it's no coincidence, since proofs and programs turned out to be the same thing :) https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspondence https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspon...
- deleted 10y ago
  [deleted]
chriswarbo 10y ago
BrainFuck is quite far removed from a Turing Machine. In BrainFuck, the "data" (the memory cells being mutated by the program) are completely separate from the code. As a consequence, BrainFuck code cannot self-modify and it has to maintain two pointers (instruction pointer and memory pointer). BrainFuck also allows the instruction pointer to jump arbitrarily far (i.e. from a "]" back to the corresponding "["). In constrast, a Turing Machine makes no separation between code and data; it just has a tape (the machine's transition table is more like a language's interpreter than a program). Not only can a program modify itself, for many tasks it must; since the tape only advances one cell at a time, moving between two arbitrary cells requires the contribution of all those in between; whenever we traverse a cell, we must also modify it in preparation for any subsequent traversal. Whilst BrainFuck is certainly a nice idea, I don't think it's the best example of anything in particular. I wrote up some thoughts on this a few years ago http://chriswarbo.net/blog/2014-12-22-minimal_languages.html http://chriswarbo.net/blog/2014-12-22-minimal_languages.html
- teraflop 10y ago
  > In constrast, a Turing Machine makes no separation between code and data; it just has a tape (the machine's transition table is more like a language's interpreter than a program). I think you're conflating "Turing machine" with "universal Turing machine". In a standard Turing machine, the state transition table is the "code". That code could be an interpreter for another language, including for arbitrary Turing machines, or it could be something entirely different. Either way, it's static, just like a Brainfuck program. In fact, the translation from Brainfuck to a Turing machine is trivial: if each cell of the tape is a byte, then each character of the program becomes one state of the machine.
tromp 10y ago
> what Lisp is to Lambda calculus It's more like what Binary Lambda Calculus is to lambda calculus. See my IOCCC entry http://www.ioccc.org/2012/tromp/tromp.c http://www.ioccc.org/2012/tromp/tromp.c http://www.ioccc.org/2012/tromp/hint.html http://www.ioccc.org/2012/tromp/hint.html which happens to include a Brainfuck interpreter...
MaulingMonkey 10y ago
This sounds like an excellent excuse to plug my Brainfuck IDE. http://maulingmonkey.com/brainfuck/ http://maulingmonkey.com/brainfuck/ Ahh... it's a work in progress. I should probably add an option to disable my optimization passes, for starters...

by exDM69 10y ago

nickpsecurity 10y ago

I've always thought the Turing LISP was Forth. It's a tiny, stack machine with few ops plus some LISP capabilities. Also implemented in efficient hardware.

bogomipz 10y ago
Is Turing Lisp a flavor of LISP? This is the first I've heard of it.
- nickpsecurity 10y ago
  Turing Machines and Lambda Calculus are equivalent in power, but opposite in style, ways of formally describing computing. Imperative programming came from one and functional programming from the other. One of simplest... conceptually and in implementation... versions of Lambda Calculus is LISP. I'm guessing you already know what it can do. In Turing/Imperative Land, I suggested Forth comes closest to being simplest of very powerful languages. There's probably implementations of all of these in all the others out there. I'm just saying Forth is a Turing-style language with LISP-like simplicity and benefits.
  - bogomipz 10y ago
    Ah OK, thanks for the clarification. That dichotomy makes perfect sense. I haven't really looked at Forth, is your comment about its "LISP-like simplicity" why is such a perennial favorite amongst language aficionados? Any recommended readings on the subject(Forth) ?
    - nickpsecurity 10y ago
      Intro here: https://users.ece.cmu.edu/~koopman/forth/hopl.html https://users.ece.cmu.edu/~koopman/forth/hopl.html Yosefk's write-up is the definitive one for me, though, showing an intro, some amazing stuff about it, weird stuff, and reasons for ultimately not going with it. Link: http://yosefk.com/blog/my-history-with-forth-stack-machines.html http://yosefk.com/blog/my-history-with-forth-stack-machines....
- grkvlt 10y ago
  No, he means Turing machines are to FORTH as Lambda Calculus is to Lisp.
  - bogomipz 10y ago
    Thanks.

YeGoblynQueenne 10y ago

>> Brainfuck is to Turing machines what Lisp is to Lambda calculus. Indeed, the lambda calculus was never meant as a real programming language.

joelg 10y ago
> Indeed, the lambda calculus was never meant as a real programming language. In fact, not even Lisp itself was originally meant as a real programming language! McCarthy invented it as a notation for mathematical proofs, and one of his grad students thought it might make a good language.
- nickpsecurity 10y ago
  Never knew that. That's a trip. Great accident to have in one's career given all that came of it.
  - AnimalMuppet 10y ago
    http://www.paulgraham.com/icad.html http://www.paulgraham.com/icad.html Look for the section heading "Catching Up with Math".
    - nickpsecurity 10y ago
      That was a good read. Appreciate the link.
- chriswarbo 10y ago
  In hindsight it's no coincidence, since proofs and programs turned out to be the same thing :) https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspondence https://en.wikipedia.org/wiki/Curry%E2%80%93Howard_correspon...
deleted 10y ago
[deleted]

chriswarbo 10y ago

BrainFuck is quite far removed from a Turing Machine. In BrainFuck, the "data" (the memory cells being mutated by the program) are completely separate from the code. As a consequence, BrainFuck code cannot self-modify and it has to maintain two pointers (instruction pointer and memory pointer). BrainFuck also allows the instruction pointer to jump arbitrarily far (i.e. from a "]" back to the corresponding "["). In constrast, a Turing Machine makes no separation between code and data; it just has a tape (the machine's transition table is more like a language's interpreter than a program). Not only can a program modify itself, for many tasks it must; since the tape only advances one cell at a time, moving between two arbitrary cells requires the contribution of all those in between; whenever we traverse a cell, we must also modify it in preparation for any subsequent traversal. Whilst BrainFuck is certainly a nice idea, I don't think it's the best example of anything in particular. I wrote up some thoughts on this a few years ago http://chriswarbo.net/blog/2014-12-22-minimal_languages.html http://chriswarbo.net/blog/2014-12-22-minimal_languages.html

teraflop 10y ago
> In constrast, a Turing Machine makes no separation between code and data; it just has a tape (the machine's transition table is more like a language's interpreter than a program). I think you're conflating "Turing machine" with "universal Turing machine". In a standard Turing machine, the state transition table is the "code". That code could be an interpreter for another language, including for arbitrary Turing machines, or it could be something entirely different. Either way, it's static, just like a Brainfuck program. In fact, the translation from Brainfuck to a Turing machine is trivial: if each cell of the tape is a byte, then each character of the program becomes one state of the machine.

tromp 10y ago

> what Lisp is to Lambda calculus It's more like what Binary Lambda Calculus is to lambda calculus. See my IOCCC entry http://www.ioccc.org/2012/tromp/tromp.c http://www.ioccc.org/2012/tromp/tromp.c http://www.ioccc.org/2012/tromp/hint.html http://www.ioccc.org/2012/tromp/hint.html which happens to include a Brainfuck interpreter...

MaulingMonkey 10y ago

This sounds like an excellent excuse to plug my Brainfuck IDE. http://maulingmonkey.com/brainfuck/ http://maulingmonkey.com/brainfuck/ Ahh... it's a work in progress. I should probably add an option to disable my optimization passes, for starters...