Computable Function

Definition

Computable Function

The term computable function may refer to either a partial computable function or a total computable function, depending on the context and literature. Totality must therefore be stated explicitly when the distinction matters.

Partial Computable

Definition

Partial Computable Function

A partial function is partial computable (p.c.) if there exists a URM program such that, for every input tuple ,

and whenever it halts, its output is .

The set is the domain on which is defined. The program must halt and return the correct value there; outside it, the program never halts. A partial computable function may also be total.

Computational model

This definition fixes the URM as its computational model. Using Turing machines instead gives the same class of functions; this equivalence is a theorem.

The Church–Turing thesis identifies this formal class with the effectively computable functions.

Link to original

Total Computable

Definition

Total Computable Function

A function is total computable (t.c.) if it is partial computable and total:

Thus a URM program computing must halt and return on every input tuple .

Link to original

Course terminology

In Logic and Foundations of Mathematics, berechenbar often abbreviates total computable (lecture slides, slide 30). Broader headings also use it for computability in general; p.c. and t.c. distinguish the two precisely.

Example

Not every total Boolean function is computable

The statement “For every total function , there exists a Turing machine that computes ” is false.

There are uncountably many such functions, but only countably many Turing machines. Hence most such functions are uncomputable.