Computable Function

In Computability Theory computable functions or '''Turing-computable functions''' are the basic objects of study. They make our intuitive notion of Algorithm precise and according to the Church–Turing Thesis they are exactly the functions that can be calculated using a mechanical calculation device. The notion of computability of a function can be Relativized to an arbitrary Set of Natural Number s ''A'', or equivalently to an arbitrary function ''f'' from the naturals to the naturals, by using Turing machines extended by an Oracle for ''A'' or ''f''. Such functions may be called '''''A-computable''''' or '''''f-computable''''' respectively.
Before the precise definition of computable function Mathematician s often used the informal term ''effectively computable''.

Computable functions are used to discuss computability without referring to any concrete Model Of Computation like Turing machines or register machines. The Blum Axioms can be used to define an abstract Computational Complexity Theory on the set of computable functions.

According to the Church–Turing Thesis , the class of computable functions is equivalent to the class of functions defined by Recursive Function s, Lambda Calculus , or Markov Algorithm s.

Alternatively they can be defined as those algorithms that can be calculated by Turing Machine s, Post System s, or Register Machine s.

In Computational Complexity Theory , the problem of determining the complexity of a computable function is known as a Function Problem .

DEFINITION

A Partial Function
:

f:\subseteq \mathbb{N} 	o \mathbb{N}

is called computable if the Graph of

f

is a Recursively Enumerable Set . The set of partial computable functions with one parameter is usually denoted

\mathbf{P}^{(1)}

\mathbf{P}

if the number of parameters is clear from the context.

A Total Function
:

f:\mathbb{N} 	o \mathbb{N}

is called computable if the graph of

f

is a Recursive Set . The set of total computable functions with one parameter is usually denoted

\mathbf{R}^{(1)}

\mathbf{R}

.

A computable function

f

is called computable predicate if it is Boolean Valued , that is
:

f:\subseteq \mathbb{N} 	o \{0,1\}

REMARKS

Sometimes, for reasons of clarity, we write a computable function as
:

g:\subseteq \mathbb{N}^k 	o \mathbb{N}

We can easily encode ''g'' into a new function
:

f:\subseteq \mathbb{N} 	o \mathbb{N}

using a Pairing Function .

EXAMPLES

Constant Function ''f'' : N^''k''→ N, ''f''(''n''₁,...''n''_''k'') := ''n''

Addition ''f'' : N²→ N, ''f''(''n''₁,''n''_''2'') := ''n''₁ + ''n''₂

Greatest Common Divisor

Bézout's Identity , a linear Diophantine Equation

PROPERTIES

The Set of computable functions is Countable .

Given two computable functions ''f'' and ''g'' then ''f''+''g'', ''fg'' and ''f''o''g'' are computable functions.

Computable functions are Arithmetically Definable .

A boolean-valued function ''f'' is a computable predicate if and only if the language $\{x \in \Sigma^{---} : f(x)=1\}$ is Recursive .

	APPAREL
	BABY
	BEAUTY
	BOOKS
	CAR TOYS
	CELL PHONES
	DVD'S
	ELECTRONICS
	GOURMET FOOD
	GROCERIES
	HEALTH & PERSONAL
	HOME & GARDEN
	JEWELRY
	MUSIC
	MUSIC INSTRUMENTS
	OFFICE PRODUCTS
	SOFTWARE
	SPORTING GOODS
	TOOLS & HARDWARE
	TOYS
	VIDEO GAMES
	SHOPPING HOME

	MORE SHOPPING...

	CATEGORIES ABOUT COMPUTABLE FUNCTION

	recursion theory

	theory of computation

Information About

Computable Function