I'm not sure if the idea I have about them is right or wrong.My professor defines four possible actions a Turing machine can do on a given input string:Hang: The turing machine goes off the left end of the tape and "hangs"Loop: The turing machine goes in a loop- never haltsAccepts: Turing machine halts in an accepting stateRejects: Turing machine halts in a rejecting stateIs a turing recognizable language simply one that may either hold or loop? How do I determine if it could cling or loop? simply run it thru the system and if it does not halt on the rejecting state (or accepting) and its not part of the language of the TM then I determine its not decidable- so it must be recognizable? and then the decider is that if the language is assured to just accept or reject? What about languages that aren't recognizable? What might they do? as it seems that every one languages would be recognizable until it would be viable for the language to now not be inside the language of the turing system- but it halts inside the accepting kingdom anyways. Which looks like it would be because of bad layout of the turing system as opposed to the language itself.

Question

I&#039;m not sure if the idea I have about them is right or wrong.My professor defines four possible actions a Turing machine can do on a given input string:Hang: The turing machine goes off the left end of the tape and &quot;hangs&quot;Loop: The turing machine goes in a loop- never haltsAccepts: Turing machine halts in an accepting stateRejects: Turing machine halts in a rejecting stateIs a turing recognizable language simply one that may either hold or loop? How do I determine if it could cling or loop? simply run it thru the system and if it does not halt on the rejecting state (or accepting) and its not part of the language of the TM then I determine its not decidable- so it must be recognizable? and then the decider is that if the language is assured to just accept or reject? What about languages that aren&#039;t recognizable? What might they do? as it seems that every one languages would be recognizable until it would be viable for the language to now not be inside the language of the turing system- but it halts inside the accepting kingdom anyways. Which looks like it would be because of bad layout of the turing system as opposed to the language itself.

Hofpoetb9 · Accepted Answer

A language L is said to be recursively enumerable if there exists a Turing Machine M satisfying the following conditions:-For every   ω  ∈  L, simulating M on   ω (which we denote M(  ω)) results in M halting and accepting   ω. -For every   ω  ∈      Σ          ∗        ∖  L, M does not accept ω.Note that for a recursively enumerable language, any TM accepting L need not halt on inputs outside of the language.If L is decidable, there must exist some TM that halts on all inputs in addition to the conditions for L being recursively enumerable.What about languages that aren&#039;t recognizable?No such decider or recognizer would exist. Consider the following language:       L          N      O      T      −      H      A      L      T        =  {  ⟨      M          i        ⟩  ,      ω          i        :      M          i       is the ith TM and       ω          i       is the ith string in       Σ          ∗       and       M          i       does not halt on       ω          i        }.The language       L          N      O      T      −      H      A      L      T       is not recursively enumerable. No TM can accept every string in       M          i      . For some TMs in       L          N      O      T      −      H      A      L      T      , it may be possible to recognize an infinite loop by checking the states and transition function. However, there is no general procedure to do this for all TMs in       L          N      O      T      −      H      A      L      T      . A Cantor diagonal argument proves this. See the undecidability of the halting problem.

Answered question

Answer & Explanation

New Questions in High school statistics