A proof that Unix utility "sed" is Turing complete

catonmat.net

23 pointsAnon848 comments

There isn't much here except a sed program and a printout demonstrating 151 being incremented once.

I improved the article a little. Take a look now.

Thanks, I found the link to the busy beaver problem, and go my money's worth. But seriously, that was an interesting post.

Can we also prove that awk is Turing complete this way?

That'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!

Shrug Even more people are surprised that Excel is Turing complete.

That's not entirely a fair comparison as Excel contains a complete VB environment.

awk has while loops, conditionals, variables, and associative arrays. It's Turing-complete.

Reply on news.ycombinator.com