**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.

Lecture# Theory of Computability and Halting Problem

Description

This lecture introduces the theory of computability, focusing on decision problems that require a 'yes' or 'no' answer for each value. The instructor explains the halting problem, which questions if an algorithm will terminate in finite time. Turing's 1936 demonstration shows that an algorithm predicting this does not exist.

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.

In course

In MOOCs (2)

Instructors (3)

Related concepts (24)

CS-119(a): Information, Computation, Communication

D'une part, le cours aborde: (1) la notion d'algorithme et de représentation de l'information, (2) l'échantillonnage d'un signal et la compression de données et (3) des aspects
liés aux systèmes: ordi

Dans une première partie, nous étudierons d’abord comment résoudre de manière très concrète un problème au moyen d’un algorithme, ce qui nous amènera dans un second temps à une des grandes questions d

Dans une première partie, nous étudierons d’abord comment résoudre de manière très concrète un problème au moyen d’un algorithme, ce qui nous amènera dans un second temps à une des grandes questions d

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.

In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whether a given natural number is prime. Another is the problem "given two numbers x and y, does x evenly divide y?". The answer is either 'yes' or 'no' depending upon the values of x and y. A method for solving a decision problem, given in the form of an algorithm, is called a decision procedure for that problem.

In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. The halting problem is undecidable, meaning that no general algorithm exists that solves the halting problem for all possible program–input pairs. A key part of the formal statement of the problem is a mathematical definition of a computer and program, usually via a Turing machine.

Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since expanded to include the study of generalized computability and definability. In these areas, computability theory overlaps with proof theory and effective descriptive set theory.

In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is proved to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. The halting problem is an example: it can be proven that there is no algorithm that correctly determines whether arbitrary programs eventually halt when run. A decision problem is a question which, for every input in some infinite set of inputs, answers "yes" or "no"..

Related lectures (12)

Undecidability: Recursive Languages and Turing Machines

Explores undecidability through recursive languages, Turing machines, and the halting problem.

Theory of Computability: Solvability and Complexity

Explores the theory of computability, decision problems, complexity classes, and the 'P vs. NP' conundrum.

Halting Problem: Unsolvable ProblemsCS-101: Advanced information, computation, communication I

Explores the unsolvability of the halting problem in algorithms and the limitations of procedures in determining program halting.

Theory of Computation: Undecidable ProblemsCS-119(d): Information, Computation, Communication

Explores the existence of functions that cannot be computed, illustrated by famous paradoxes and the concept of undecidable problems.

Algorithms: Halting Problem QuizCS-101: Advanced information, computation, communication I

Explores the Halting Problem, efficient list element positioning, and the cashier's algorithm.