3 ms·
A proof that Unix utility "sed" is Turing complete
- politician 15y agoThere isn't much here except a sed program and a printout demonstrating 151 being incremented once.
- pkrumins 15y agoI improved the article a little. Take a look now.
- politician 15y agoThanks, I found the link to the busy beaver problem, and go my money's worth. But seriously, that was an interesting post.
- rollypolly 15y agoCan we also prove that awk is Turing complete this way?
- pkrumins 15y agoThat's not the point. Many people are surprised when they hear that sed is Turing complete. How come a text filtering program is Turing complete they ask? Turns out sed is like a small assembly language that has a comparison operation, a branching operation and a temporary buffer. If you translate a problem into a textual representation then these operations are enough to make sed Turing complete!
- mturmon 15y agoawk has while loops, conditionals, variables, and associative arrays. It's Turing-complete.