MFCS: Problem set 2

A postscript version is available. Please check the postscript version if some symbol is not decipherable

1. Let c be any number. Show that the following problems are undecidable.

   the input or Acceptance problem:

   ` ' ` ' ` '.

   the output or Printing problem:

   ` ' ` '.

2. Show that the following problems are undecidable:
   1. ` '
   2. ` '
   3. ` '
   4. ` '
   5. ` '
   6. ` '
   7. ` '
   8. ` '
   9. ` ', where g is any fixed computable function.
3. Show that there is no total computable function f(x,y) with the following property: if stops, then it does so in f(x,y) or fewer steps.

• About this document ...