Computable

A Partial Function is called computable if there is a register machine such that .

We say that a Partial Numerical Function is computable if and only if its encoding is computable.

A set is computable if its Characteristic Function is computable. This works both for and . It further works when we are Encoding Alphabets in Binary Words

Proposition

The class of computable Formal Languages is closed under union, intersection, complement, and concatenation.