1
$\begingroup$

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.