Lecture

Theory of Computation: Counting and Decision Problems

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Description

This lecture covers the theory of computation, focusing on counting infinite sets and decision problems. It discusses the concept of countability, demonstrating how to count infinite sets like positive integers and pairs of positive integers. The lecture also explores the notion of decidability, distinguishing between decidable and undecidable problems. It presents examples of decidable problems, such as checking if a number is a multiple of another, and introduces the undecidable halting problem. Through demonstrations of self-reference and paradoxes, the lecture illustrates the limitations of computation in solving certain problems. It concludes by emphasizing the significance of recognizing undecidable problems and the power of self-reference in computational theory.

This video is available exclusively on Mediaspace for a restricted audience. Please log in to MediaSpace to access it if you have the necessary permissions.

Watch on Mediaspace

Official source

Ontological neighbourhood

Mathematics

Mathematical logic: Set theory

Related concepts (32)

Countable set

In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is countable if there exists an injective function from it into the natural numbers; this means that each element in the set may be associated to a unique natural number, or that the elements of the set can be counted one at a time, although the counting may never finish due to an infinite number of elements.

Decision problem

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.

Infinite set

In set theory, an infinite set is a set that is not a finite set. Infinite sets may be countable or uncountable. The set of natural numbers (whose existence is postulated by the axiom of infinity) is infinite. It is the only set that is directly required by the axioms to be infinite. The existence of any other infinite set can be proved in Zermelo–Fraenkel set theory (ZFC), but only by showing that it follows from the existence of the natural numbers.

Dedekind-infinite set

In mathematics, a set A is Dedekind-infinite (named after the German mathematician Richard Dedekind) if some proper subset B of A is equinumerous to A. Explicitly, this means that there exists a bijective function from A onto some proper subset B of A. A set is Dedekind-finite if it is not Dedekind-infinite (i.e., no such bijection exists). Proposed by Dedekind in 1888, Dedekind-infiniteness was the first definition of "infinite" that did not rely on the definition of the natural numbers.

Undecidable problem

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 (62)

Relations, Sequences and Summations

Covers strings, countable sets, cardinality, and the concept of countability, exploring the countability of various sets and Cantor diagonalization.

Separable L^2 Spaces

Covers the concept of separable L^2 spaces, demonstrating properties and providing examples.

Fractals and Strange Attractors

Delves into renormalization, fractals, and strange attractors, exploring the properties of countable and uncountable sets.

Probability Theory: Lecture 2

Explores toy models, sigma-algebras, T-valued random variables, measures, and independence in probability theory.

Nonlinear Dynamics: Chaos and Complex Systems