next up previous
Next: Substitutionprimitive recursion and Up: MFCS: Problem set 1 Previous: MFCS: Problem set 1

URM programs

  1. Show that the following functions are computable by devising programs that compute them.
    1. displaymath101

    2. displaymath102

    3. displaymath103

    4. displaymath104

    5. Suppose that P is a program without jump instructions. Show that there is a number m such that either tex2html_wrap_inline127 or tex2html_wrap_inline129
    6. 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.)
  2. Show that the following predicates are decidable:
    1. `x ;SPMlt; y'
    2. ` tex2html_wrap_inline137 '
    3. `x is even'


Subhashis Banerjee
Fri Sep 5 15:54:45 IST 1997