Hacker News Reader

> Then again, no real computer is Turing complete because they all have finite memory so they're strictly speaking only big finite state machines (though we do typically consider them Turing complete anyway).

Memory is only finite if it uses absolute addresses like RAM, e.g. "load 0x12345" refers to the same piece of memory, regardless of where in memory that instruction appears (ignoring complications from paging, etc.). Computers can also have external storage that's addressed relatively, e.g. a tape which can move forwards or backwards.

I like to think of Turing machines has having a "tape factory" at both ends of the tape, which appends new cells whenever the read/write head gets close. We can do the same thing with a real computer, by pausing the computer and splicing on new sections on to the tape as needed; or by extending the rails and racks of a tape robot.

Of course, our factories are ultimately limited by raw materials, even once production expands into space. The key is that relatively-addressed memory is infinitely expandable, whilst absolutely-addressed memory has a predefined upper-limit.

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!

> 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".

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

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...

> I think the main point here is that the context/prediction model of JPEG XL's modular mode is expressive enough to consider it a kind of mini-programming language which is 'Turing-complete' (with some asterisks like requiring infinite images).

Yes, this is exactly the point I intended. I have added a link Gwern Branwen's https://www.gwern.net/Turing-complete for context. (I considered adding a note on how no physical computer or interpreter running on one is really Turing-complete before submitting the story but decided against it, because the context should convey the asterisks on "Turing-complete".)

I have also quoted your paragraph on security on the page. Something I did not consider was that people may link to my page to support security FUD against JPEG XL, a format I like and look forward to adopting. I hope this is sufficient mitigation.

> Then again, no real computer is Turing complete because they all have finite memory so they're strictly speaking only big finite state machines

Interestingly, cloud computing made this limitation less obvious: one can imagine a program running on the cloud that bill the cloud provider when it runs out of disk space. And the cloud provider will buy more hard drives for its servers when needed. There is still obviously a limit somewhere, but its much farther ahead, because its more limited by factors such as how much hard drives we can build.

Let me rephrase: the observable universe is strictly speaking not Turing-complete :)

I don't think we knows that for sure either.

If the universe is expanding indefinitely, then it means it has unlimited potential to store information, for example as the position of matter inside the universe.

For example imagine a spacecraft going away from earth, with a mirror toward the earth. On earth you can send a stream of bits with a laser toward it and it will come back. As it goes farther and farther away, you can increase the amount of bits in transit in the stream, making it a way to store a potentially infinite amount of bits.

Of course this is not a really good example, because I'm sure there is a lots of reasons why this scheme would not work indefinitely, such as chaos theory preventing us to target the spacecraft with the every-growing precision required.

But still, I would love to see an actual reasoning of wether or not the information we can store in the universe is actually bounded.

You'll run out of energy to power the laser.

Even if you could somehow recycle energy forever, more and more of your initial energy supply will be locked up in the laser beam. By e=mc², building an always-growing laser beam is equivalent to building an always-growing tape. Even if it's more efficient by a very big constant factor, that's still a constant factor.

You would need a magic box that supplies watts out of nowhere to keep this scheme working. But if you had one of those, it might be easier to just convert some of the output into matter to feed a very slow tape-building machine.

Assuming a finite universe, I'll just use 100% of the possible memory for my program. Now you can't run my program and count the steps.