The shortest non-halting brainfuck program will have exactly three instructions. Here is one them: `+[]` here is another one: `-[]`. Brainfuck's state consis

The shortest non-halting brainfuck program will have exactly three instructions. Here is one them: `+[]` here is another one: `-[]`. Brainfuck's state consists of an array of integers, an index into that array, a program counter, and some bookkeeping required to track which "[" corresponds to which "]". Let's assume the array a[:] is zeroed and the index i is set to 0 before the program begins executing. Then `+` increments the cell in the array a at index i, i.e. `a[i] += 1`; `[` begins a while loop, equivalent to `while a[i] != 0 {`; and `]` ends the while loop: `}` . So the program `+[]` is equivalent to something like a := (allocate a length N array of bytes, set to zero) i := 0 a[i] += 1 while a[i] != 0 { } which will not terminate. Why is this the shortest? `]` is the only instruction that might decrease the program counter, otherwise the program counter always increases by one or more. Therefore, a non-halting brainfuck program must include at least one `]`. Brainfuck programs are syntactically incorrect unless there is exactly one `]` occurring somewhere in the program after each `[`. So the shortest non-halting brainfuck program must have at least two instructions. There is only one syntactically valid brainfuck program with two instructions that might not halt: `[]`. But this will halt, assuming that the array `a` is initialised to zero before execution begins. So the shortest non-halting brainfuck program contains three instructions.