Tail pad optimization, cache friendlyness and C++ interrop

[via Digitalmars-d]

On Wednesday, 18 June 2014 at 15:25:11 UTC, Luís Marques wrote:
> Maybe I missed something in this discussion, but unless you are
> not including jumps/loops in those N instructions, just because
> the number of instructions and memory is bounded does not mean
> you can prove (for arbitrary programs) that the program
> terminates.

Yes, you can. You just run it until it enters a previous state. 
At that point you have an infinite loop and it won't terminate.

Since you only have a finite number of possible states and you 
always move from one state to another the proof of this becomes 
trivial. The worst case time complexity is the same as the number 
of possible states.