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

split the tape into 2 halves; the tape to the left of the head is one stack, the tape to the right of the head is the other stack.

Head moving long the tape is just popping from one stack and pushing onto the other. The head state (and other bookkeeping) can be encoded in the DFA.



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

Search: