# All Science Fair Projects

## Science Fair Project Encyclopedia for Schools!

 Search    Browse    Forum  Coach    Links    Editor    Help    Tell-a-Friend    Encyclopedia    Dictionary

# Science Fair Project Encyclopedia

For information on any area of science that interests you,
enter a keyword (eg. scientific method, molecule, cloud, carbohydrate etc.).
Or else, you can start by choosing any of the categories below.

# 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 mechanic calculation device.

Before the precise definition of computable function mathematicians often used the informal term effectively computable.

 Contents

## Definition

Generally a computable function is a partial function

$f:\subseteq \mathbb{N} \to \mathbb{N}$

The class of computable functions is equivalent to the class of functions defined by

Alternatively they can be defined as those algorithms that can be calculated by

## Notes

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

$g:\subseteq \mathbb{N}^k \to \mathbb{N}$

We can easily encode g into a new function

$f:\subseteq \mathbb{N} \to \mathbb{N}$

using a pairing function.

## Properties

• The set of computable functions is countable.
• Given two computable functions f and g then f+g, fg and fog are computable functions.
03-10-2013 05:06:04