**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Concept# Computability

Summary

Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is closely linked to the existence of an algorithm to solve the problem.
The most widely studied models of computability are the Turing-computable and μ-recursive functions, and the lambda calculus, all of which have computationally equivalent power. Other forms of computability are studied as well: computability notions weaker than Turing machines are studied in automata theory, while computability notions stronger than Turing machines are studied in the field of hypercomputation.
A central idea in computability is that of a (computational) problem, which is a task whose computability can be explored.
There are two key types of problems:
A decision problem fixes a set S, which may be a set of strings, natural numbers, or other objects taken from some larger set U. A particular instance of the problem is to decide, given an element u of U, whether u is in S. For example, let U be the set of natural numbers and S the set of prime numbers. The corresponding decision problem corresponds to primality testing.
A function problem consists of a function f from a set U to a set V. An instance of the problem is to compute, given an element u in U, the corresponding element f(u) in V. For example, U and V may be the set of all finite binary strings, and f may take a string and return the string obtained by reversing the digits of the input (so f(0101) = 1010).
Other types of problems include search problems and optimization problems.
One goal of computability theory is to determine which problems, or classes of problems, can be solved in each model of computation.
Model of computation
A model of computation is a formal description of a particular type of computational process. The description often takes the form of an abstract machine that is meant to perform the task at hand.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related publications (1)

Non-malleable codes are a generalization of classical error-correcting codes where the act of "corrupting" a codeword is replaced by a "tampering" adversary. Non-malleable codes guarantee that the mes

Related people

No results

Related units

No results

Related concepts (33)

Church–Turing thesis

In computability theory, the Church–Turing thesis (also known as computability thesis, the Turing–Church thesis, the Church–Turing conjecture, Church's thesis, Church's conjecture, and Turing's thesis) is a thesis about the nature of computable functions. It states that a function on the natural numbers can be calculated by an effective method if and only if it is computable by a Turing machine. The thesis is named after American mathematician Alonzo Church and the British mathematician Alan Turing.

Register machine

In mathematical logic and theoretical computer science, a register machine is a generic class of abstract machines used in a manner similar to a Turing machine. All the models are Turing equivalent. The register machine gets its name from its use of one or more "registers". In contrast to the tape and head used by a Turing machine, the model uses multiple, uniquely addressed registers, each of which holds a single positive integer.

Computability

Computability is the ability to solve a problem in an effective manner. It is a key topic of the field of computability theory within mathematical logic and the theory of computation within computer science. The computability of a problem is closely linked to the existence of an algorithm to solve the problem. The most widely studied models of computability are the Turing-computable and μ-recursive functions, and the lambda calculus, all of which have computationally equivalent power.

Related courses (11)

MATH-381: Mathematical logic

Branche des mathématiques en lien avec le fondement des mathématiques et l'informatique théorique. Le cours est centré sur la logique du 1er ordre et l'articulation entre syntaxe et sémantique.

CS-251: Theory of computation

This course constitutes an introduction to theory of computation. It discusses the basic theoretical models of computing (finite automata, Turing machine), as well as, provides a solid and mathematica

MATH-351: Advanced numerical analysis

The student will learn state-of-the-art algorithms for solving differential equations. The analysis and implementation of these algorithms will be discussed in some detail.

Related lectures (106)

Convergence Analysis: Explicit RK Scheme

Explores the convergence analysis of the Explicit Runge-Kutta scheme for accurate numerical solutions.

Nerves and Geometric Realization

Covers the explicit computations of nerves of categories and geometric realisations of simplicial sets.

Theory of Computability and Halting Problem

Covers the theory of computability and the halting problem in algorithms.

Related MOOCs

No results