logoalt Hacker News

nyrikkilast Monday at 2:19 PM1 replyview on HN

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.


Replies

conradevlast Monday at 2:49 PM

Cook and Mertz call the wider area they work on “catalytic computing”: https://www.quantamagazine.org/catalytic-computing-taps-the-...