A recursively enumerable set whose complement is also recursively enumerable is recursive

by ariels (4.1 hr)

Sun Sep 02 2001 at 10:50:13

An exercise giving the relationship between recursively enumerable sets and recursive sets.

Suppose both a language L and its complement L' are recursively enumerable. Then there exist Turing machines M and M' such that M halts precisely on inputs from L, and M's halts precisely on inputs from L'. Consider a Turing machine N which takes as input a word x simulates the runs of M(x) and M'(x) "simultaneously" (i.e. it performs one step of each computation in some interleaved manner). Obviously, (exactly) one of the computations will terminate (either x is in L or it's in L'!). N outputs `1' (x∈L) if M(x) terminates, and `0' if M'(x) does.

Hence L is recursive: N decides membership of L.

(I like it!)

printable version

chaos

recursively enumerable	Post's correspondence problem	recursive	Turing Machine
your mom	recursive case	base case	Enumeration
Nodeshell Challenge	twos complement	semi-Thue grammar	UN
Rice's Theorem	Heckler and Koch date codes	exercise

Y'know, if you log in, you can write something here, or contact authors directly on the site. Create a New User if you don't already have an account.

Everything2

A recursively enumerable set whose complement is also recursively enumerable is recursive

Epicenter

Cool Staff Picks

New Writeups

Login
Password