===========================================================================
CSC 363                     Homework Exercise 3                   Fall 2008
===========================================================================

Due: by 2pm on Wed 15 Oct
Worth: 1.5%

For each question, please write up detailed answers carefully: make sure
that you use notation and terminology correctly, and that you explain and
justify what you are doing.  Marks *will* be deducted for incorrect or
ambiguous use of notation and terminology, and for making incorrect,
unjustified, ambiguous, or vague claims in your solutions.


1.  Is the following language decidable, undecidable but recognizable, or
    unrecognizable?  Prove your answer.
        BA_TM = { <M,w,t> : M is a TM that accepts input w
                  within t steps of computation }


2.  Is the following language decidable, undecidable but recognizable, or
    unrecognizable?  Prove your answer.
        NL_TM = { <M,w> : M is a TM whose head *never* moves left
                  during its computation on input w }