News for hackers. Stuff that matters.
Re:Common Expression Language by blonde_ocean on Thursday December 10, 2020 @07:39PM (#25380848)
How do you mean sub-Turing languages don’t allow recursion? Aren’t context-free languages, for example, literally recursive?
Re:Common Expression Language by remexre on Thursday December 10, 2020 @09:07PM (#25381416)
"Arbitrary recursion" is the correct claim; e.g. Coq allows recursion, but has restrictions so all programs terminate.
Re:Common Expression Language by codebje on Thursday December 10, 2020 @09:13PM (#25381448)
I assume GP means general recursion.

Recursion in a pushdown automata (the equivalent machine for a CFL) is bounded by the input words being consumed, since each state transition consumes one input token. Since all input words are finite, indefinite recursion is excluded.