Turing decidable and recognizable languages

Turing Recognizable

The language recognized by Turing Machine (or language of is the set of input strings accepts.

A language is Turing recognizable if a TM recognizes it.

We say two Turing Machines are equivalent if they recognize the same language.

Turing Decidable

A decider is a Turing Machine that halts on all inputs. A language is Turing decidable if a decider recognizes it.

If a decider recognizes a language, we additionally say it decides that language

• There is a language that is not recognizable.
• There is a recognizable language that is not decidable

Closure Properties

See also: closure property

Closure properties are useful for proving recognizability or decidability of languages by applying set operations on languages whose status is already known.

Decidable Languages

• The union of decidable languages is decidable.
• The intersection of decidable languages is decidable.
• If a language is decidable then so is its complement.

Recognizable Languages

• The union of recognizable languages is recognizable.
• The intersection of recognizable languages is recognizable.

Important

the complement of a recognizable language is not necessarily recognizable!

Relationship between Decidable and Recognizable

• A language is decidable if and only if when and its complement are recognizable.