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

Any textbook on formal languages and automata. Michael Sipser’s is my favorite. Church Turing Thesis is sophomore CS stuff..

Two stacks can simulate a Turing Tape. E.g. moving left is simulated by popping off one stack and pushing onto other. One counter can encode the tape while the other is used to encode the tape position.



Consider applying for YC's Winter 2027 batch! Applications are open till November 2.

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

Search: