3 ms·

Bits are a bit misleading here, it would be more accurate to say "units of computation". If you're problem space operates on 32-bit integers this would be 32bit

Bits are a bit misleading here, it would be more accurate to say "units of computation". If you're problem space operates on 32-bit integers this would be 32bits * number of steps, these papers solve for individual bits as the smallest individual unit of computation we can commonly reason about.

mort96 1y ago
Wait but if "bits of memory" here was supposed to be "units of computation", that means that: * The old assumption was that if you require t steps to complete, you need t/log(t) units of computation * This new proof shows that if you require t steps to complete, you need sqrt(t) units of computation Surely this doesn't make sense? Using any definition of "unit of computation" I would intuitively assume, computing t steps requires something proportionalt to t units of computation...
- nyrikki 1y ago
  There is a bit of nuances here that is difficult to explain fully but note from the paper. > Our simulation reduces the problem of simulating time-bounded multitape Turing machines to a series of implicitly-defined Tree Evaluation instances with nice parameters, leveraging the remarkable space-efficient algorithm for Tree Evaluation recently found by Cook and Mertz [STOC 2024]. The "time-bounded multitape Turing machines" with bounded fan-in means that that particular abstract model has access to the bits of those tapes current head position. Mapping the quirks of the various abstract models can be tricky, but remember having access to the symbol currently under the tape head is 'free' in TMs. It is a useful abstraction but doesn't directly map to physically realizable machine. It is still an interesting result for trees in physically realizable machines.
  - conradev 1y ago
    Cook and Mertz call the wider area they work on “catalytic computing”: https://www.quantamagazine.org/catalytic-computing-taps-the-full-power-of-a-full-hard-drive-20250218/ https://www.quantamagazine.org/catalytic-computing-taps-the-...

mort96 1y ago

Wait but if "bits of memory" here was supposed to be "units of computation", that means that: * The old assumption was that if you require t steps to complete, you need t/log(t) units of computation * This new proof shows that if you require t steps to complete, you need sqrt(t) units of computation Surely this doesn't make sense? Using any definition of "unit of computation" I would intuitively assume, computing t steps requires something proportionalt to t units of computation...

nyrikki 1y ago
There is a bit of nuances here that is difficult to explain fully but note from the paper. > Our simulation reduces the problem of simulating time-bounded multitape Turing machines to a series of implicitly-defined Tree Evaluation instances with nice parameters, leveraging the remarkable space-efficient algorithm for Tree Evaluation recently found by Cook and Mertz [STOC 2024]. The "time-bounded multitape Turing machines" with bounded fan-in means that that particular abstract model has access to the bits of those tapes current head position. Mapping the quirks of the various abstract models can be tricky, but remember having access to the symbol currently under the tape head is 'free' in TMs. It is a useful abstraction but doesn't directly map to physically realizable machine. It is still an interesting result for trees in physically realizable machines.
- conradev 1y ago
  Cook and Mertz call the wider area they work on “catalytic computing”: https://www.quantamagazine.org/catalytic-computing-taps-the-full-power-of-a-full-hard-drive-20250218/ https://www.quantamagazine.org/catalytic-computing-taps-the-...