Turing Decidable and Recognizable Languages

TMs and Infinite Loops

• Question: If a TM is given a string, what can happen to the computation?


• Answer: The machine can either
1. Accept the string (ie enter the Accept state and halt the computation)


2. Reject the string (ie enter the Reject state and halt the computation)


3. Enter an Infinite Loop (ie the computation never ends)

Looping on a String

• We say that a machine loops on a string if the string puts the machine into an infinite loop


• When a machine loops, it never enters the Accept state or the Reject state


• When a machine loops, it transitions forever among states that are neither the Accept state nor the Reject state

Looping and DFA, NFA, PDA

• In the context of TMs and looping, it's useful to think about looping for all of our machines.


• Can a DFA M loop?
• No: a computation halts when the end of the input is reached


• Can an NFA loop?
• Yes: a computation can make epsilon transitions forever
• But, every NFA has an equivalent DFA that doesn't loop


• Can a PDA loop?
• Yes: a computation can make epsilon transitions forever
• But, every PDA has an equivalent PDA that halts on all input
• Create a grammar that accepts the same language as the PDA
• Create a PDA for that grammar
• This PDA will halt on all strings [true, but not proved]


• Can an TM loop?
• Yes: a computation can make epsilon transitions forever
• The TM is a recognizer and not a decder
• If TM M accepts L and M loops on some w ∈ L^C, is it possible to make a TM M' accepts L and that halts on all w ∈ L^C?
• Sometimes, but not always.
• That is, sometimes you can create a decider, sometimes not

Languages Accepted by DFA, NFA, PDA

• In the context of TMs and looping, it's useful to think about the language accepted (and accepting the complement) for all of our machines.


• DFA M:
• L = L(M) = {w| M's unique computation on w reaches accept state}
• L^C = {w| M's unique computation on w reaches non-accept state}


• NFA N:
• L = L(N) = {w| Some computation on w reaches an accept state}
• L^C = {w| NO computation on w reaches an accept state}
• Can determine if w ∈ L^C using the equivalent DFA


• PDA P:
• L = L(P) = {w| Some computation on w reaches an accept state}
• L^C = {w| NO computation on w reaches an accept state}
• Can we determine if w ∈ L^C using the equivalent PDA that halts on all inputs? No.
• Can't simply swap states - why?
• CFL not closed under complement.


• TM:
• L = L(M) = {w| Some computation on w reaches the Accept state}
• L^C = {w| NO computation on w reaches an accept state}
• A computation that doesn't reach the Accept state can either
• Reach the Reject state
• Loop
• Can we tell if w ∈ L^C:
• If it's possible to build a decider, then yes.
• If not, then not always.
• For some TM, it's impossible to build a decider for the machines language.

Looping and Defining Languages

• The possibility of looping affects how we define the relationship between a machine and the language it defines


• TM M recognizes language L iff
  1. the strings L put M into the Accept state
  2. the strings NOT IN L
  • EITHER put M into the Reject state
  • OR cause M to loop
  
  
• TM M decides language L iff
  1. the strings L put M into the Accept state
  2. the strings NOT IN L put M into the Reject state

Recognizers and Deciders

• A recognizer of a language is a machine that recognizes that language
• A decider of a language is a machine that decides that language


• Both types of machine halt in the Accept state on strings that are in the language
• A Decider also halts if the string is not in the language
• A Recogizer MAY or MAY NOT halt on strings that are not in the language


• On all input:
• A Decider MUST halt (in Accept or Reject state)
• A Recogizer MAY or MAY NOT halt on some strings (Q: Which ones?)


• Is every Recognizer a Decider, or is every Decider a Recognizer?


• Finish this statement: TM M decides language L if M recognizes L and it also ...


• It's useful to look at two subset diagrams:
1. All string > strings L^C, string L=L(M) for recognizer M
2. All string > strings L^C, string L=L(M) for decider M

Examples

• Think about the Turing machines for these languages:
• aⁱb^jc^k


• w#w


• Are they deciders or recognizers?
• Answer: Both

Recognizers

• Examples of recognizers that aren't deciders?


• If L has a Decider D, can we find a machine R that recognizes L but that does not decide it?
• It's easy
• How can we modify the previous examples.


• Another question: Can we find L that has a recognizer but not a decider?
• Yes, as we will see later


• First, define some more terms: TR and TD languages

Definition: Turing Decidable Language

• A language is Turing-decidable (or decidable) if some Turing machine decides it


• Aka Recursive Language

Review: Turing Recognizable Language

• A language is Turing-recognizable if some Turing machine recognizes it


• Aka Recursively Enumerable Language

Showing that a Language is Decidable/Recognizable

• How do we show that a language is TD: Build a decider for it
• How do we show that a language is TR: Build a decider or recognizer for it


• How do we show that language L is TR and not TD:
• Build a Recognizer for L
• PROVE that there is no Decider for l
• We will see examples soon

Relationship among Language Classes

• How do these language classes fit togther
• Regular
• Context Free
• Turing Decidable
• Turing Recognizable


• (We haven't yet proved the relation between CF and TD langs)


• What are some examples in each class (and not in smaller class)?
• First three are easy: Regular, CF, decidable
• Are there languages that are recognizable but NOT decidable?
• Are the languages that are NOT recognizable?