# decidability (under construction)

(2.9 hours to learn)

## Summary

-No Summary-

## Notes

This concept is still under construction.

## Context

This concept has the prerequisites:

- Turing machines (Turing machines are the canonical model of computation when reasoning about decidability.)
- countable sets (A simple counting argument shows that not all languages are decidable.)

## Goals

- Define the sets of decidable and recursively enumerable languages.

- Be able to show that some simple languages are decidable.

- Prove, using a counting argument, that not all languages are decidable.

- Prove that the halting problem is undecidable.

- Prove that the universal language is recursively enumerable.

## Core resources (read/watch one of the following)

## -Free-

→ Coursera: Automata

An introductory course on automata and the theory of computation.

Location:
Lecture "Decidability"

Other notes:

- Click on "Preview" to see the lecture videos.

## -Paid-

→ Introduction to the Theory of Computation

An undergraduate textbook on automata and the theory of computation.

Location:
Chapter 4, "Decidability," pages 165-182

Other notes:

- The material about regular and context-free languages is optional (and depends on earlier chapters).

→ Automata Theory, Languages, and Computation

An undergraduate textbook on automata and the theory of computation.

- Section 8.1, "Problems that computers cannot solve," pages 315-324
- Section 9.1, "A language that is not recursively enumerable," pages 378-382
- Section 9.2, "An undecidable problem that is RE," pages 383-390

## See also

-No Additional Notes-