Edit Question - KnowledgeHub

Title Body

I have written a simple brainfuck 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. So, I need a mechanism to detect infinite loops and avoid executing that code in bf. One obvious (trivial) case is when I have [] I can detect this and refuse to run that program. 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. 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. ) ++++ 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 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. Can anyone think of a good algorithm to detect infinite loops, given arbitrary nesting of arbitrary number of loops in bf? 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

Tags (comma-separated) Cancel