I know well the distinction between the class of Partial Recursive Functions, and $\mu$-Recursive, i.e. the latter is Turing Complete and the former is equivalent to the LOOP-Program model of computation.

So, LOOP programs are equivalent to an imperative language with assignment, if and for loops with computable upper bounds. Now, I wanna know two things:

1) Is there a model that corresponds to a language without iteration and with only assignment and selection (if) ? 2) Is there a model that use only assignment and arithmetic or logic expressions on int variables?

The question arise since, I was considering the transition from liner straight program with only assignment and arithmetic and bitwise operators, to the one that include if. I suppose that functions like abs or max, min, cannot be computable without a selection than I realized that simple logical expression like: x ^ ((x ^ y) & -(x < y)); compute the max. So basically max is computable by a very simple circuit. Now I would like to know, is there some function that require the 'conditional' to be computable or not?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.