News for hackers. Stuff that matters.
Re:JPEG XL would be Turing-complete without the 1024×1024 pi... by sp332 on Monday June 21, 2021 @11:09AM (#27579927)
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!
Re:JPEG XL would be Turing-complete without the 1024×1024 pi... by Dylan16807 on Monday June 21, 2021 @01:35PM (#27581485)
> 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".

Re:JPEG XL would be Turing-complete without the 1024×1024 pi... by hajile on Wednesday June 23, 2021 @01:30PM (#27607305)
The halting problem can exist in bounded memory. A jump instruction that jumps to itself would be the most simple example.
Re:JPEG XL would be Turing-complete without the 1024×1024 pi... by sp332 on Wednesday June 23, 2021 @04:15PM (#27609636)
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...