HN Explorer

8 comments

[ 3.0 ms ] story [ 29.1 ms ] thread
politician
There isn't much here except a sed program and a printout demonstrating 151 being incremented once.
pkrumins
I improved the article a little. Take a look now.
politician
Thanks, I found the link to the busy beaver problem, and go my money's worth. But seriously, that was an interesting post.
rollypolly
Can we also prove that awk is Turing complete this way?
pkrumins
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!

yzhengyu
Shrug Even more people are surprised that Excel is Turing complete.
wladimir
That's not entirely a fair comparison as Excel contains a complete VB environment.
mturmon
awk has while loops, conditionals, variables, and associative arrays. It's Turing-complete.