FIT2014 Lecture Notes - Lecture 18: If And Only If, Recursively Enumerable Language, Universal Turing Machine
29 Jun 2018
School
Department
Course
Professor
Lecture 18: : Recursively Enumerable
A language L is decidable if and only if there exists a Turing Machine T such that
Definition: recursively enumerable
A language L is recursively enumerable if there exists a Turing machine T such that Accept(T) = L
Strings outside L may be rejected, or may make T loop forever.
recursively enumerable (r.e.)
= computably enumerable
= partially decidable
= Turing recognisable (used in Sipser)
= type 0 (in Chomsky hierarchy)
Decidable versus r.e.
Every decidable language is recursively enumerable.
Is every recursively enumerable language decidable?
Consider: HALT = { T : T halts, if input is T } (diagonal halting problem)
This is the language corresponding to the Halting Problem. We know it’s not decidable.
Halting Problem is Recursive Enumerable
Let M be a Turing machine which takes, as input, a Turing machine T and
- simulates what happens when T is run with itself as its input,
- If T stops/ halt (in any state), M accepts
Here, M could be obtained by modifying a Universal Turing machine
Accept(M) = HALT
Reject(M) = Ø as it is keep running and stimulate
Loop(M) = 𝐻𝐴𝐿𝑇
̅
̅
̅
̅
̅
̅
̅
̅
So HALT is recursively enumerable. So some recursively enumerable languages are not decidable.
Enumerators
An enumerator is a Turing machine which outputs a sequence of strings.
This can be a finite or infinite sequence. If it’s infinite, then the enumerator will never halt.
It never accepts or rejects; it just keeps outputting strings, one after another. If the sequence is finite, then
the enumerator may stop once it has finished outputting. But the state it enters doesn’t matter.)
A language L is enumerated by an enumerator
M if L = { all strings in the sequence outputted by M }
Document Summary
A language l is decidable if and only if there exists a turing machine t such that. A language l is recursively enumerable if there exists a turing machine t such that accept(t) = l. Strings outside l may be rejected, or may make t loop forever. recursively enumerable (r. e. ) Consider: halt = { t : t halts, if input is t } (diagonal halting problem) This is the language corresponding to the halting problem. Let m be a turing machine which takes, as input, a turing machine t and simulates what happens when t is run with itself as its input, If t stops/ halt (in any state), m accepts. Here, m could be obtained by modifying a universal turing machine. Reject(m) = as it is keep running and stimulate. So some recursively enumerable languages are not decidable. An enumerator is a turing machine which outputs a sequence of strings. This can be a finite or infinite sequence.
