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