Recursive Language

languages

Definition

Recursive Language

A language is recursive (or decidable) if there exists a total Turing machine such that, for every input , halts and:

1. if , accepts ;
2. if , rejects .

Equivalently:

• The characteristic function is computable.
• Both and its complement are recursively enumerable.
• There exists a program that, given any string , decides membership in finite time.

Equivalence with Decision Problem

Decision Problem Recursive Language

Let a decision problem have instances in some set and “yes”-instances .

Fix a computable encoding . Define the language of the problem:

Then:

Decision Problem Recursive Language

: If has a decider , build a Turing machine that on input :

: decode to ; if decoding fails, reject; else run and accept iff “yes”.

: If has a decider , then the algorithm for is:

: on instance , run on and answer “yes” iff accepts.