Hacker News new | ask | show | jobs
by Dylan16807 2873 days ago
Interesting, but my thoughts were along a simpler route of making a literal Turing machine out of text.

Represent your tape with digits, and your head with a letter. Have an arrow from the letter to the active cell.

  [ 0 0 0 1 1 A->2 2 2 ]
Then the text replacements look like this

  A->2 becomes 1 A->

  2<-A becomes 1 A->

  B->2 becomes <-D 3

  2<-B becomes <-D 3
So two text replacements for every state/symbol combo. And the halt state has no replacements. Easy!

(Plus a replacement from [<- to [0<- and from ->] to ->0] to make the tape infinite.)