Mediaspace scheduled maintenance: Aug 25, 2026 07:00 - 12:00 AM. During this time, videos will be temporarily unavailable. Check status updates.

Lecture

Theory of Computation: Problems Definition and Counting (Denumerability)

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.

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.

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.

Related lectures (37)

Algorithms & Growth of Functions

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

Theory of Computation: Undecidable Problems

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

Theory of Computation: Counting and Decision Problems

Explores counting infinite sets and decision problems, showcasing the limits of computation in solving certain undecidable problems.

Relations, Sequences and Summations

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

Finite Systems Expressed with Formulas