5. "Island of computability" and Computable Functions

What does Bijective mean?

A type of function that establishes a perfect, one-to-one correspondence between 2 sets

What does countably infinite mean?

You can create a list or a process to identify each element of the set, even if the list never ends.

Whrn is a set countably infinite?

If there exists a bijective function N = {0, 1, 2, …} → S

When is a set countable?

If it is finite, or countably infinite

True or false, the integers are countable

True

True or false, the rational numbers are not countable

False

True or false, the real numbers are uncountable (and explain why)

True: irrational numbers cannot be counted.

What is the idea of Hilberts Hotel, and give an equation that visualises it.

A hotel with countably infinite numbers of rooms can accomadate infinitely many coachloads of countably infinite passengers each.

Prove that if S is any infinite set, then 2^s is countable

By contradiction.

S is countably infinite, as otherwise 2^S is clearly uncountable.

Assume 2^S is countably infinite

Then there is an infinite listing S₀, S₁, …. of the elements of 2^S (that is, of all the subsets of S). Also, since S is countably infinite, there is a bijective function f: N → S. Hence the subsets of S can be represented by an infinite matrix of the following type.

Is 2^(Σ*) countable or uncountable, and why?

Uncountable - Σ* is infinite

What is Cantors diagonal argument and give the formal description

The inverse of the diagonal is different from every row.

Subset D of S: D = {f (i) | i ≥ 0 and f (i !∈ Si}

Represented by the inverse of the diagonal of the matrix. Since D ⊆ S, there must be some n ≥ 0 such that S_n = D. We consider two cases.

Case 1: f(n) ∈ S_n. Then, by definition of D, f (n) !∈ D = S_n. A contradiction.

Case 2: f (n) !∈ S_n. Then, by definition of D, f (n) ∈ D = S_n. Again a contradiction.

Thus our assumption that 2^s is countably infinite must be wrong, hence 2^s is uncountable.

Prove for every alphabet Σ, there are uncountably many languages over Σ that are not semidecidable.

Every semidecidable language over Σ is accepted by some TM. Since TMs can be encoded as strings in {0, 1}* with the injective encoding e, and {0,1}* is countably infinite, the set of all TMs with input alphabet Σ is countable as well. Hence the set of all semidecidable languages over Σ is countable too. But 2^(Σ*), the set of all languages over Σ is uncountable by above.

2^(Σ^)− {L ⊆ Σ | L is semidecidable} is also uncountable

Where is f_M(x) undefined

1. M diverges (”loops”)

2. M halts in state hr

3. M halts with the tape head not on square 1