Next: Substitutionprimitive recursion and
Up: MFCS: Problem set 1
Previous: MFCS: Problem set 1
 Show that the following functions are computable by devising
programs that compute them.




 Suppose that P is a program without jump instructions. Show that
there is a number m such that either
or
 Show that for each transfer instruction T(m,n) there is a
program without transfer instructions that has exactly the same effects
as T(m,n) on any configuration of the URM. (Thus transfer
instructions are really redundant in the formulation of URM; it is
nevertheless convenient to have transfer as a basic facility of
the URM.)
 Show that the following predicates are decidable:
 `x ;SPMlt; y'
 ` '
 `x is even'
Subhashis Banerjee
Fri Sep 5 15:54:45 IST 1997