Theory of comp questions

Discussion in 'OT Technology' started by mrburner, Apr 1, 2004.

  1. mrburner

    mrburner Ron Paul 2008

    May 9, 2001
    Likes Received:
    alright, i've been working on this assignment for awhile but these are the two i couldn't if someone could point me in the right direction, it would be appreciated

    1. L9 = {<M, w> | M is a TM, M on input w moves its head left at some point during its computation on w}. Show that L9 is decidable.

    2. L10 = {<M, w> | M is a TM, at some point in its computation, M on input w moves its head left when the head is on the left-most tape cell}. Show that L10 is not decidable.

    thanks in advance
  2. crotchfruit

    crotchfruit Guest

    well, i have no fucking clue what these questions are about. however, i will take a shot in the dark.

    L9 is decidable, as in, you can tell if operation w occurred, because you are guaranteed that M moves its head to the left. so if M moves it's head to the left, w was input.

    L10 is not decidable because w could be input without you knowing (if the head is not on the left-most tape cell.) therefore you cannot know if w was input.


Share This Page