CVE-2021-32471 – Input validation in Marvin Minsky 1967 Turing Machine

Post by mousepilot » Tue, May 11, 2021, 12:38 PM UTC

klyrs wrote: post #39

zitterbewegung wrote: post #37

Earlier quoted context omitted.

You can't do anything like recursion.

I spent a while trying to parse this, and it doesn't make a lick of sense. Brainfuck is a classical example of a turing complete language that doesn't have a notion of functions. What does "recursion" mean here? Nothing, I think. So you don't need recursion for Turing completeness. Some people work on languages that support functions as first class objects, which don't natively support recursion. This is nice from a…

Post by mousepilot » Tue, May 11, 2021, 6:22 PM UTC

klyrs wrote: post #42

mousepilot wrote: post #41

Earlier quoted context omitted.

I'm not that great a programmer, but this one seems easy to me, you write an interpreter in brainfuck that allows function definitions that support recursion, then include your recursive function definitions as an included constant then point your interpreter at the constant and tell it to run it. I assume bf allows constants but like I said I'm not that great a programmer. Obviously using a recursive descent parser…

> I assume bf allows constants but like I said I'm not that great a programmer. Key to being a good programmer: at least read a bit about the language before speculating about it. Not sure what you mean by "allows constants", but you're only given increment and decrement operators, and a promise that fresh tape is zeroed out. Brainfuck supports iteration. Performing recursion in a higher level language will still loo…