Turing completeness, and generation of non-Turing complete code to solve problems that would typically require Turing complete languages

Hi,

This message may seem somewhat cryptic, but I am trying to abstract
from particulars relating to a particular non-Turing complete language
to general matters.

In most languages if one has some data in a field of text consisting of
a certain length which has to be analysed in some way (for example
detecting if parts of the line have specific values) it is normal to
loop or recurse through the line until the end is reached, and
determining if all the relevant parts of the line are as they should
be.

In a non-Turing complete language this may not be doable (I suppose
most non Turing Complete languages lack looping or recursing abilities,
but there may be some that have these but lack other things).

However if one knows the upper bound of the data, for example knowing
the exact length of the data one can generate a program in a non-Turing
complete language to handle the problem.

The problem that I specifically had that led me to doing this was:

A field of text that can be up to 43 lines in length, no line greater
than 35 characters in length. Lines have been normalized to a linefeed.


Solution using non-Turing complete:
Generate code consisting of splitting string at linefeeds, if string
between linefeed 1 and 2 not greater than 35 and not less than 1 do not
raise error, if string between linefeed 2 and 3 not greater than 35 and
not less than 1 do not raise error... and so forth.

Because of the nature of the language, which was a rule based one,
rules for linefeeds analysis greater than the number of linefeeds in my
actual data were not called thus not creating error conditions.


What I'm wondering is if there are any studies on the Generation of
Non-Turing complete code via Turing complete languages to run against
data where the bounds are known as in this situation? Can one prove
that code which can solve any computation can be generated for a
language that is Non-Turing complete by a Turing Complete language?

What features must a non-Turing complete language lack in order for it
to be impossible to generate code in it to handle any calculation?

Are there special requirements for the language in which code is
generated? As in the example above where I know the possible upper
bound of the data but in which data that did not reach this point did
not raise an error because the rules were not called.

.

Relevant Pages

  • Re: About avoiding reinventing the wheel
    ... book length introduction to SML. ... you cannot easily find an answer from an introductory book, ... the language was Haskell, not SML. ... What's the reason for 'raise' being ...
    (comp.lang.functional)
  • Re: CFO: Why C?
    ... Paul Pluzhnikov wrote: ... >>must ask for a raise, ... If it can't have #ifdefs then it is not C. ... the language doesn't it. ...
    (comp.os.linux.development.apps)
  • Re: Paul Grahams Arc is released today... what is the long term impact?
    ... I'd have thought that the others would not raise ... a> passions. ... a> that there are some more fundamental differences that I'm missing. ... but Paul brands his language as totally new, and so he can promote his style ...
    (comp.lang.lisp)
  • Re: How often do you read the C standard?
    ... in parentheses saves time wasted on minutiae, i.e., ... doesn't raise any "what does that do" responses. ... programming productivity. ... I would not call the C language well defined; ...
    (comp.lang.c)
  • Re: "I call and raise $50" technically not allowed?
    ... _REAL_ casinos" ... most dealers would say "Please don't say 'I call' when you want to raise." ... Just learn what is correct and use that language. ... terminology for whatever game they are playing. ...
    (rec.gambling.poker)