StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PODetecting infinite loop in brainfuck program
text
Body
copied!<p>I have written a simple <a href="http://en.wikipedia.org/wiki/Brainfuck" rel="noreferrer">brainfuck</a> interpreter in MATLAB script language. It is fed random bf programs to execute (as part of a genetic algorithm project). The problem I face is, the program turns out to have an infinite loop in a sizeable number of cases, and hence the GA gets stuck at the point.<br> So, I need a mechanism to detect infinite loops and avoid executing that code in bf.<br> One obvious (trivial) case is when I have</p> <pre><code>[] </code></pre> <p>I can detect this and refuse to run that program.<br> For the non-trivial cases, I figured out that the basic idea is: to determine how one iteration of the loop changes the current cell. If the change is negative, we're eventually going to reach 0, so it's a finite loop. Otherwise, if the change is non-negative, it's an infinite loop.<br> Implementing this is easy for the case of a single loop, but with nested loops it becomes very complicated. For example, (in what follows (1) refers to contents of cell 1, etc. )</p> <pre><code>++++ Put 4 in 1st cell (1) >+++ Put 3 in (2) <[ While( (1) is non zero) -- Decrease (1) by 2 >[ While( (2) is non zero) - Decrement (2) <+ Increment (1) >] (2) would be 0 at this point +++ Increase (2) by 3 making (2) = 3 <] (1) was decreased by 2 and then increased by 3, so net effect is increment </code></pre> <p>and hence the code runs on and on. A naive check of the number of +'s and -'s done on cell 1, however, would say the number of -'s is more, so would not detect the infinite loop.<br> Can anyone think of a good algorithm to detect infinite loops, given arbitrary nesting of arbitrary number of loops in bf?</p> <p>EDIT: I do know that the halting problem is unsolvable in general, but I was not sure whether there did not exist special case exceptions. Like, maybe Matlab might function as a Super Turing machine able to determine the halting of the bf program. I might be horribly wrong, but if so, I would like to know exactly how and why. </p> <p>SECOND EDIT: I have written what I purport to be infinite loop detector. It probably misses some edge cases (or less probably, somehow escapes Mr. Turing's clutches), but seems to work for me as of now. In pseudocode form, here it goes:</p> <pre><code>subroutine bfexec(bfprogram) begin Looping through the bfprogram, If(current character is '[') Find the corresponding ']' Store the code between the two brackets in, say, 'subprog' Save the value of the current cell in oldval Call bfexec recursively with subprog Save the value of the current cell in newval If(newval >= oldval) Raise an 'infinite loop' error and exit EndIf /* Do other character's processings */ EndIf EndLoop end </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload