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

What Turing complete means is that given an infinite amount of memory and time, a language can simulate anything that is computable.

Change "simulate" to "compute" and I agree fully. I don't think it's necessary to introduce the concept of simulation. If a language (or process, mechanism or whatever) is Turing Complete, then you can use it to express all things computable. Given sufficient resources, that expression could actually do the computation.

edit: I recalled in a sibling post why simulation comes up, and I think it's a source of confusion. The easiest way to prove a formalized process is Turing complete is to simulate a Turing machine. Since a Turing machine can compute all that is computable, and your process can simulate a Turing machine, your process can compute all that is computable. Hence, it is Turing complete.




Applications are open for YC Summer 2015

Guidelines | FAQ | Support | API | Lists | Bookmarklet | DMCA | Y Combinator | Apply | Contact

Search: