Hacker News new | past | comments | ask | show | jobs | submit login

Can you elabrate on why a growable tape has more limited computational power than an infinite tape (is the growth you have in mind constrained in some way?)

Not that we could have the latter, or an unconstrained version of the former, in our temporal world, of course!





I see, so by 'growable' you don't mean arbitrarily growable or growable-as-needed without restriction. That would have overturned my intuitions in these matters.


I’m not confident in my ability to explain it more clearly. However I highly recommend reading Sipser[1] because his treatment of the subject, and many others, is as clear as can be.

[1] https://www.goodreads.com/book/show/400716.Introduction_to_t...


Thanks - this is new to me.




Join us for AI Startup School this June 16-17 in San Francisco!

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: