Lecture

Theory of Computation: Problems Definition and Counting (Denumerability)

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 introduces the theory of computation, focusing on problems definition and counting. It covers the concept of denumerability, explaining how to count infinite sets and showcasing examples of countable and uncountable sets. The instructor discusses the importance of algorithms in solving problems and highlights the distinction between countable algorithms and uncountable functions. Through examples, the lecture illustrates how some boolean functions cannot be computed by any algorithm, emphasizing the limitations of computation in handling certain types of problems.

Official source

Related concepts (32)

Boolean function

In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually {true, false}, {0,1} or {-1,1}). Alternative names are switching function, used especially in older computer science literature, and truth function (or logical function), used in logic. Boolean functions are the subject of Boolean algebra and switching theory. A Boolean function takes the form , where is known as the Boolean domain and is a non-negative integer called the arity of the function.

Boolean expression

In computer science, a Boolean expression is an expression used in programming languages that produces a Boolean value when evaluated. A Boolean value is either true or false. A Boolean expression may be composed of a combination of the Boolean constants true or false, Boolean-typed variables, Boolean-valued operators, and Boolean-valued functions. Boolean expressions correspond to propositional formulas in logic and are a special case of Boolean circuits.

Boolean algebra

In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values true and false, usually denoted 1 and 0, whereas in elementary algebra the values of the variables are numbers. Second, Boolean algebra uses logical operators such as conjunction (and) denoted as ∧, disjunction (or) denoted as ∨, and the negation (not) denoted as ¬.

Boolean differential calculus

Boolean differential calculus (BDC) (German: Boolescher Differentialkalkül (BDK)) is a subject field of Boolean algebra discussing changes of Boolean variables and Boolean functions. Boolean differential calculus concepts are analogous to those of classical differential calculus, notably studying the changes in functions and variables with respect to another/others. The Boolean differential calculus allows various aspects of dynamical systems theory such as automata theory on finite automata Petri net theory supervisory control theory (SCT) to be discussed in a united and closed form, with their individual advantages combined.

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.

Related lectures (33)

Algorithms & Growth of Functions

Covers optimization algorithms, stable matching, and Big-O notation for algorithm efficiency.

Momentum Methods and Nonlinear Conjugate Gradients

The session explains how momentum accelerates gradient descent, presents the theory of nonlinear conjugate gradients on manifolds, compares several beta‑rule updates, discusses line‑search and preconditioner choices, and shows how to employ the Manopt library for Riemannian optimization without explicit Hessians.

Complexity & Induction: Algorithms & Proofs

Covers worst-case complexity, algorithms, and proofs including mathematical induction and recursion.

Theory of Computation: Undecidable Problems

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

Relations, Sequences and Summations