Comment

Comment by LPisGood

I think it is very intuitive that more space beats the pants off of more time.

In time O(n) you can use O(n) cells on a tape, but there are O(2^n) possible configurations of symbols on a tape of length n (for an alphabet with 2 symbols), so you can do so much more with n space than with n time.

parent LPisGood 1 year ago

Discussion

Live from the official Hacker News API

A modern reader for Hacker News · SvelteKit + Skeleton