5 ms·

> First note that to get to interesting classes, i.e. everything above regular languages / finite state automata (FSA), you need infinite memory. When you have

> First note that to get to interesting classes, i.e. everything above regular languages / finite state automata (FSA), you need infinite memory. When you have finite memory, it is always only just as powerful as a FSA. While this is true, I'd like to point out that this distinction is purely theoretical. Nothing infinite exists in the real world, but some things are so plentiful we might consider them infinite for the sake of easier reasoning. A very practical example of this is cloud computation. All data centers in the world obviously have a finite amount of memory, however, the amount is so huge that for the sake of any practical computation, we might as well consider them infinite (though we are more limited by the money required than by the physical resources themselves).

pavlov 4y ago
When is it useful to assume infinite computing resources in the cloud? I'm struggling to come up with an example.
- bheadmaster 4y ago
  You assume infinite resources every time you create an unbounded queue, for example.
  - pavlov 4y ago
    But in a real-world application of course I have to think about the queue's capacity and bandwidth limits and monitor accordingly. Assuming infinite anything in production would be a time bomb of tech debt.
    - bheadmaster 4y ago
      While I see where you coming from, the whole "scalability" story is about assuming infinite resources and scaling your usage as the demand spikes. Kubernetes (I think) is specialized in that regard - assuming you can create a potentially infinite number of instances, you create a system that consumes as much resources as it needs for fulfilling the demand.
BlueTemplar 4y ago
Actually, time (and maybe space) are infinite (countably so, thanks to Heisenberg's Uncertainty Principle) ? Energy probably isn't though (maybe it is, if space is ?), that is going to put a limit on non-reversible computation ?
- danbruc 4y ago
  Actually, time (and maybe space) are infinite (countably so, thanks to Heisenberg's Uncertainty Principle) ? Not a physicist, so better get a second opinion, but I do not think that this is something you can get out of the uncertainty principle. As far as I can tell it does not turn continuous space and time into some discrete voxel space, i.e. while there is uncertainty, the location of the peak of the amplitude, for example, can still be located anywhere in continuous space. Energy probably isn't though (maybe it is, if space is ?), that is going to put a limit on non-reversible computation ? The total energy of the universe might be zero. [1] [1] https://en.wikipedia.org/wiki/Zero-energy_universe https://en.wikipedia.org/wiki/Zero-energy_universe
  - m_dupont 4y ago
    Physicist here. You are correct. The uncertainty principle doesnt turn space into some sort of voxel grid. While we still don't know what spacetime looks like at the smallest scales (we're still waiting on a quantum theory of gravity), quantum field theory measures spacetime using continuous real numbers
    - naasking 4y ago
      > While we still don't know what spacetime looks like at the smallest scales (we're still waiting on a quantum theory of gravity), quantum field theory measures spacetime using continuous real numbers IIRC, the uncertainty principle limits the precision in any possible measurement to something like 60 or 70 digits. So yes, current theories use continuous real numbers, but I wouldn't generalize that to say that's confirmed because we're nowhere near being able to test that level of precision.
jltsiren 4y ago
The distinction is very practical. It's better to think about it in terms of hard-coded limits vs. arbitrary scaling than finite vs. infinite. Anything designed to handle n items needs "infinite" memory. Language classes are about the code, not about the computer. With a finite state automaton, you have to commit to the size of the input in advance and write the state transitions explicitly. While there exist structurally similar automata that can handle larger inputs, your automaton – your code – cannot handle them. You can generate those automata algorithmically, but in order to do that, you need a more expressive formalism that can handle n items.

pavlov 4y ago

When is it useful to assume infinite computing resources in the cloud? I'm struggling to come up with an example.

bheadmaster 4y ago
You assume infinite resources every time you create an unbounded queue, for example.
- pavlov 4y ago
  But in a real-world application of course I have to think about the queue's capacity and bandwidth limits and monitor accordingly. Assuming infinite anything in production would be a time bomb of tech debt.
  - bheadmaster 4y ago
    While I see where you coming from, the whole "scalability" story is about assuming infinite resources and scaling your usage as the demand spikes. Kubernetes (I think) is specialized in that regard - assuming you can create a potentially infinite number of instances, you create a system that consumes as much resources as it needs for fulfilling the demand.

BlueTemplar 4y ago

Actually, time (and maybe space) are infinite (countably so, thanks to Heisenberg's Uncertainty Principle) ? Energy probably isn't though (maybe it is, if space is ?), that is going to put a limit on non-reversible computation ?

danbruc 4y ago
Actually, time (and maybe space) are infinite (countably so, thanks to Heisenberg's Uncertainty Principle) ? Not a physicist, so better get a second opinion, but I do not think that this is something you can get out of the uncertainty principle. As far as I can tell it does not turn continuous space and time into some discrete voxel space, i.e. while there is uncertainty, the location of the peak of the amplitude, for example, can still be located anywhere in continuous space. Energy probably isn't though (maybe it is, if space is ?), that is going to put a limit on non-reversible computation ? The total energy of the universe might be zero. [1] [1] https://en.wikipedia.org/wiki/Zero-energy_universe https://en.wikipedia.org/wiki/Zero-energy_universe
- m_dupont 4y ago
  Physicist here. You are correct. The uncertainty principle doesnt turn space into some sort of voxel grid. While we still don't know what spacetime looks like at the smallest scales (we're still waiting on a quantum theory of gravity), quantum field theory measures spacetime using continuous real numbers
  - naasking 4y ago
    > While we still don't know what spacetime looks like at the smallest scales (we're still waiting on a quantum theory of gravity), quantum field theory measures spacetime using continuous real numbers IIRC, the uncertainty principle limits the precision in any possible measurement to something like 60 or 70 digits. So yes, current theories use continuous real numbers, but I wouldn't generalize that to say that's confirmed because we're nowhere near being able to test that level of precision.

jltsiren 4y ago

The distinction is very practical. It's better to think about it in terms of hard-coded limits vs. arbitrary scaling than finite vs. infinite. Anything designed to handle n items needs "infinite" memory. Language classes are about the code, not about the computer. With a finite state automaton, you have to commit to the size of the input in advance and write the state transitions explicitly. While there exist structurally similar automata that can handle larger inputs, your automaton – your code – cannot handle them. You can generate those automata algorithmically, but in order to do that, you need a more expressive formalism that can handle n items.