Undecidabe Problems

Problems solved using Turing Machine

Design a Turing Machine to accept the language L = {anbn | n>=1}.  Draw the transition diagram for the same

State Transition Diagram for the TM

State Transition Table for the TM 

Processing the string "aaabbb" given as input to the TM

Undecidable Problems

We can divide problems that can be solved by a Turing Machine (TM) into two:

1.  Problems that can be solved by a Turing Machine using an algorithm and the TM halts whether or not it accepts its input

2.  Problems that are only solved by Turing Machine (TM) that may run forever on inputs they do not accept.  This class of problems are undecidable, since no matter how long the TM runs, we can't know whether the input is accepted or not.

Undecidable problems can be defined as a class of problems for solving which there is no algorithm defined, even though they can be solved using a Turing Machine that fails to halt on some inputs.

 A Language that is not Recursively Enumerable:

A language ‘L’ is said to be a recursively enumerable language if there exists a Turing machine which will accept (and therefore halt) for all the input strings which are in ‘L’ but may or may not halt for all input strings which are not in ‘L’.

A language L is Recursively Enumerable (RE) if L = L(M) for some TM (M).  Recursively Enumerable languages are languages accepted by a TM that always halts, regardless of whether or not it accepts.  

The meaning of the word 'recursive' in this context is 'decidable'.  Thus, the problems that can be solved by a Turing Machine that halts after processing the given input is known as Recursively Enumerable or Decidable.