[eru]

> [...] at least, I don't think it reduces to the halting problem [...]

It does. But the halting problem is solvable for specific instances, e.g. if you are writing the programmes.