Conference rusure::math

    Here's one.  The variables are X0, X1, X2, X3, ... and they can
    hold arbitrary nonnegative integers.  The inputs are the initial
    values of [some subset of] the variables and the outputs are the
    final values of [some subset of] the variables.  A program is a
    statement, where statements are one of:
    
         ZERO variable                ! sets a variable to 0
         INCREMENT variable           ! increments a variable
         LOOP variable DO statement   ! execute statement exactly n
                                      ! times, where n is the value
                                      ! of the variable at the start
                                      ! of the loop
         BEGIN statement ; ... statement END
    
    1) Every valid program of this type will halt.
    2) Any program only references finitely many of the variables.
    3) The value of each variable at program termination is a primitive
       recursive function of the input values of all of the variables
       referenced by the program
    4) Every primitive recursive function can be computed by a program
       of this type.
    5) Ackermann's function cannot be computed by a program of this
       type.  (Ackermann's function is one example of a recursive
       function that is not primitive recursive.)
    
    Example:  Compute in X0 the value (if X1 = X2 then 1 else 0)
    
    BEGIN
    ZERO X3 ; LOOP X1 DO INCREMENT X3 ; ! Now X3 = X1
    ZERO X4 ; LOOP X2 DO INCREMENT X4 ; ! Now X4 = X2
    LOOP X1 DO BEGIN
               ZERO X6 ; INCREMENT X6 ; ZERO X7 ;
               LOOP X4 DO BEGIN
                          INCREMENT X7 ;
                          LOOP X6 DO BEGIN ZERO X7 ; ZERO X6 END
                          END ; ! Now X7 = (if X4 > 0 then X4 - 1 else 0)
               ZERO X4 ; LOOP X7 DO INCREMENT X4 ! We've subtracted one
               END ! Now X4 = (if X1 < X2 then X2 - X1 else 0)
    LOOP X2 DO BEGIN
               ZERO X6 ; INCREMENT X6 ; ZERO X7 ;
               LOOP X3 DO BEGIN
                          INCREMENT X7 ;
                          LOOP X6 DO BEGIN ZERO X7 ; ZERO X6 END
                          END ; ! Now X7 = (if X3 > 0 then X3 - 1 else 0)
               ZERO X3 ; LOOP X7 DO INCREMENT X3 ! We've subtracted one
               END ! Now X3 = (if X2 < X1 then X1 - X2 else 0)
    ! If X1 = X2 then both X3 and X4 are zero
    !            else at least one of X3 and X4 is nonzero.
    ZERO X0 ;
    INCREMENT X0 ;
    LOOP X3 DO ZERO X0 ;
    LOOP X4 DO ZERO X0
    END

    Pretty easy once you get the hang of it! :^)

    Dan

    A long wait, but well worth it.  Thanks for the reply Daniel.
    
    I think your identification of primitive recursive functions is
    the key here, and is something that I had not realized before.
    I had gotten as far as saying that "problems whose answers were
    not deterministic" could not be solved by non-turing languges.
    Thats an ambiguous way of saying that you could not write a program
    in this language to search for an answer unknown magnitude that
    you were not sure existed.
    
    For instance, I do not think that ANY non-turing language program
    could be written to solve the question "find me the next Mersenne(sp?) 
    Prime greater than X" where 'X' is input to the program.  However
    by my definition you COULD write a non-turing language program to
    answer the question "find me the next prime greater than X".
    
    I think that you could also add conditionals to your language and
    still retain its non-turing nature.
    
    --  Barry

     Re .2

>>    I think that you could also add conditionals to your language and
>>    still retain its non-turing nature.

     Yes, that is correct.  I was just trying to show how little
     is really needed -- witness the example, which combines a
     conditional expression with an equality comparison.  You can
     add lots of things for the programmers convenience.
     However, if you add [with the obvious semantics]:

          WHILE variable IS NONZERO DO statement

     then you get the full Turing machine equivalence.

>>   "find me the next Mersenne Prime greater than X"

     Let me compare this to "find me the next Prime greater than X."
     The latter is primitive recursive because you can bound the
     search -- Euclid gave the bound X! + 1 for the next prime,
     and X! + 1 is a primitive recursive function.  But for
     Mersenne primes, it is not yet known that there are
     infinitely many.  Even if it becomes known that there are
     infinitely many Mersenne primes, then to write such a
     program in the language of reply .1 would still require some
     kind of bound on the next one.  If such a bound exists and
     you don't know it, then the program exists but you can't
     find it!

     Dan

>  For instance, I do not think that ANY non-turing language program
>  could be written to solve the question "find me the next Mersenne(sp?) 
>  Prime greater than X" where 'X' is input to the program.  However
>  by my definition you COULD write a non-turing language program to
>  answer the question "find me the next prime greater than X".

I think the following shows that you can.

Either there are an infinity of Mersenne primes, or there aren't.

If there aren't, a machine could use a fixed table to find the next one, or
yield an error if there is none.

If there are, a machine that just adds 1 to n until 2^n - 1 is prime will find
the next Mersenne prime.

I can therefore define a very simple language with just 1 statement: "find next
Mersenne prime."  It compiles, as it were, into whichever of the two above is
correct.

What I'm saying is analogous to noting that the constant function defined by
"f(n) = 1 if theorem X is true, f(n) = 0 otherwise" is always a computable
function: it's either a constant 0 or a constant 1.  We just don't know *which*
computable function it is, and it's not possible to computably determine which
it is given X.  There's no paradox here, though it feels funny.

>If there are, a machine that just adds 1 to n until 2^n - 1 is prime will find
>the next Mersenne prime.
        
        Yes, it will find the next Mersenne prime, but the point was
        (assuming there are infinitely many Mersenne primes) that the
        above is an unbounded loop, with no way of telling in advance
        how many iterations it will take to stop (much like this
        sentence) whereas when finding the next prime you can compute
        an upper bound on the loop in advance.
        
        Dan

Quite right, I misinterpreted what I was replying to.