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!
[ Parent
| on HN ]
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...