Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Why is it stretching things a little far? Non-infinite tape is, as you noted, a limit on everything we consider turing complete: this is just running at a much higher level of abstraction than your computer. You could (if you were so inclined) create a physical machine with a grid of memory that behaved according to rules defined by CSS selectors. Just because this doesn't do direct memory access and behave like the computer or a traditional TM doesn't make it not a TM. (Or, at least, any less of a TM than the computer you're using.)


The real question is if this can deal with arbitrary amounts of finite memory. That is, could I express an instance of a program that requires a trillion "units" of memory w/o constructing a new "machine" that explicitly laid it out?




Consider applying for YC's Fall 2025 batch! Applications are open till Aug 4

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

Search: