Computability Theory

Overview

Computability theory focuses on the classification of problems as either solvable or not.

Alphabets

An alphabet is any nonempty finite set. The members of an alphabet are called symbols of the alphabet. A string over an alphabet is a finite sequence of symbols from that alphabet, usually written next to one another without separation.

Then length of a string $w$ over an alphabet, denoted $|w|$, is the number of symbols $w$ contains. The empty string, denoted $ϵ$, is the string of length $0$. The reverse of $w$ is the string obtained by writing $w$ in the opposite order.

String $z$ is a substring of $w$ if $z$ appears consecutively within $w$. The concatenation of strings $x$ and $y$, written $xy$, is the string obtained by appending $y$ to the end of $x$. We say string $x$ is a prefix of string $y$ if a string $z$ exists where $xz=y$. We say $x$ is a proper prefix of $y$ if $x\ne y$.

Languages

A language is a set of strings. The complement of a language $A$ is the language consisting of all strings not in $A$. A language is prefix-free if no member is a proper prefix of another member. Likewise it is suffix-free if no member is a proper suffix of another member.

For any language $A$, the endmarked language $A⊣$ is the collection of strings $w⊣$ where $w\in A$.