On: JPEG XL would be Turing-complete without the 1024×1024 pixel limitation

[sp332]

That is an interesting point. But the halting problem is one of those things that is only problem on a literally unbounded memory. If you have a known number of bits of state available, just run the machine for 2^bits steps. Either the machine will have halted by then or it will run forever. Now 2^bits may be astronomically huge, but there's still a big gap between that and undecidable!

[Dylan16807 → sp332]

> That is an interesting point. But the halting problem is one of those things that is only problem on a literally unbounded memory.

What do you mean "but"?

If you say "trust me, there's a tape factory that will kick in once you run low on space in a zillion years and it will add on another terabyte", then you do have "literally unbounded memory".

[hajile → sp332]

The halting problem can exist in bounded memory. A jump instruction that jumps to itself would be the most simple example.

[sp332 → hajile]

The halting problem is to analyze a program and decide whether it will halt after a finite number of steps, or run forever. Your program is trivial to analyze. https://cs.wellesley.edu/~cs251/f20/notes/halt.html#the-halt...