books-programmingLanguages-programmingLanguagesChHalting

Table of Contents for Programming Languages: a survey

machines that always halt / total functions

• always halting languages: epigram, charity (i think agda also?)
• coq
• not decidable (halting problem, actually harder, because the halting problem is only 'halts on one input', and we are asking if it halts on every input)
• "Can every partial function computable by a partial Turing machine be extended (that is, have its domain enlarged) to become a total computable function? Is it possible to change the definition of a Turing machine so that a particular class of total Turing machines, computing all the total computable functions, can be found? The answer to each of these questions is no." -- https://en.wikipedia.org/wiki/Machines_that_always_halt
• primitive recursion
  • plus mu (unbounded minimization) = Turing
  • https://en.wikipedia.org/wiki/LOOP_%28programming_language%29 , http://www.lacl.fr/valarcher/Publi/fi2011.pdf http://web.archive.org/web/20120311032544/http://loopgotowhile.eugenkiss.com/
    • LOOP = addition, subtraction, (concatenation of a sequence of commands), variable assignment, LOOP (which is like a for loop). LOOP is primitive recursion.
    • LOOP + while = language called 'WHILE', Turing complete.
    • LOOP + if + goto = language called 'GOTO', Turing complete.
  • WHILE is like MIN: incr, decr, and while (i != 0) do: http://web.archive.org/web/20060713051910/http://www.dcs.shef.ac.uk/~matt/teaching/04/com2030/lectures/tomlect16.pdf (Turing-complete)
    • similar but more complicated languages with the same point as LOOP as WHILE are BlooP?