1

The Starlark configuration language does not support infinite loops or recursion or user defined data types but it does support functions. The docs indicate that means that the language is not Turing complete. I have forgotten a lot of my Computer science classes on languages and automata theory.

Questions:

  • Is the lack of user defined data types, infinite loops and recursion enough for a language to be Turing incomplete.
  • Is there a proof that StarLark is not Turing complete?
  • If a language is not Turning complete does that mean that the program is guaranteed to halt eventually?
ams
  • 60,316
  • 68
  • 200
  • 288

1 Answers1

1

  1. A Turing machine program (or any program in a Turing complete language) may never halt by falling into what is effectively an infinite loop. Ruling out nonterminating Turing machine programs is impossible (see Halting problem). Thus any language that seeks to ensure all programs terminate (such as Starlark) must sacrifice Turing completeness. See also total functional programming.

  2. See above.

  3. Not necessarily. There are other ways a language can be Turing incomplete without lacking infinite loops. For example a language where the only allowed program is while True: pass is not Turing complete, but it also does not terminate.

Jesse
  • 6,725
  • 5
  • 40
  • 45