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

• 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.