logoalt Hacker News

adgjlsfhk1 • today at 1:56 AM • 1 reply • view on HN

Have you considered looking at this in ram model rather than multi tape? it makes things a lot simpler


Replies

jdb1729 • today at 2:07 AM

For one thing, the RAM model isn't fine-grained equivalent to MTTM (an example is https://en.wikipedia.org/wiki/Counting_sort which is linear-time on RAM but not MTTM). So, the result might not be the same. But also, Mathlib lacks a RAM machine implementation. So any proof would rest on a custom definition stack which would make it difficult to audit.

➕ show 1 reply