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.

  • makelisp

• sedlisp is proof that sed is Turing complete. Not sure what constructs are used.

• Accidentally Turing Complete -- nice comprehensive list, including some games which we don't care about here

  • However, with the features Common Table Expressions and Windowing, SQL is Turing Complete.
  • Apache rewrite rules
  • sendmail
  • MediaWiki templates

• What about TeX and PostScript? I suspect those were both intended to be Turing Complete, although the syntax is odd.

• CSS3 proven to be Turing Complete --

  • https://github.com/elitheeli/stupid-machines
  • http://eli.fox-epste.in/rule110/

• 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 MMU Fault Handling

  • trapcc -- Compute with 0 instructions on Intel!

  This is a proof by construction that the Intel MMU's fault handling mechanism is Turing complete. We have constructed an assembler that translates 'Move, Branch if Zero, Decrement' instructions to C source that sets up various processor control tables. After this code has executed, the CPU computes by attempting to fault without ever executing a single instruction.

Related Issues

• Turing completeness vs. side effects/capabilities. Both of these are design issues and shouldn't be conflated.
• Whether there is abstraction power like functions. I think Awk was Turing complete at first, but it didn't have functions. Related lobsters thread.