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