Tail pad optimization, cache friendlyness and C++ interrop

[via Digitalmars-d]

On Wednesday, 18 June 2014 at 06:35:01 UTC, Ola Fosheim Grøstad
wrote:
> Not really, you can prove termination for all programs with 3 
> instructions and 3 bytes of RAM. You can do it for all programs 
> with 4 instructions and 4 bytes of RAM. You can do it for all 
> programs with N instructions and N bytes of RAM. You cannot do 
> it for all TMs since they have unbounded storage.
>
> Thus you can prove non-trivial properties such as whether a 
> functions returns with 1, whether it accepts or rejects the 
> input '0', etc. It might take a lot of time, but you can do it 
> in a fixed amount of time. You cannot do it for TMs.

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.

I hope I don't shoot myself in the foot by trying to come up with
a concrete example, but let me try. Consider the program to
calculate whether some point is part of the Mandelbrot set. The
program only requires a small and fixed amount of memory but for
some points it may iterate forever (practical fractal programs
set an iteration limit, but let's assume this one doesn't, for
the sake of the argument).