Language Design and Theory of Computation

Undecidable Parsing

Deciding whether to print "syntax error" shouldn't require simulating a Turing machine.

• Parsing Bash is Undecidable
  • Bash, Perl, and Make can't be statically parsed because they interleave parsing and execution.
  • C++ can't be statically parsed because it has two Turing complete computation mechanisms -- the templates at compile times and normal code at runtime -- and parsing sits in between them.

Accidentally Turing Complete

• Shell wasn't Turing complete when first designed.

• Make wasn't Turing complete when first designed. See Example Code in Shell, Awk, and Make.

• printf is Turing complete. %n specifier writes to memory?

  • printbf -- Brainfuck interpreter in printf

• Section 6.2.1 of http://nebelwelt.net/publications/files/15SEC.pdf

When we control the arguments to printf(), it is possible to obtain Turing-complete computation. We show this formally in Appendix B by giving calls to printf() which create logic gates.

• x86 page tables
• sendmail?

Related Issues

• Turing completeness vs. side effects.
• Whether there is abstraction power like functions. I think Awk was Turing complete at first, but it didn't have functions. Related lobsters thread.