Theory of Computation: Counting and Decision Problems

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.

About this result

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 lectures (51)

Related concepts (101)

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

L'objectif de ce cours est d'introduire les étudiants à la pensée algorithmique, de les familiariser avec les fondamentaux de l'Informatique et de développer une première compétence en programmation (

Theory of Computation: Countability & Halting Problem CS-119(c): Information, Computation, Communication

Explores countability, the halting problem, decision problems, and denumerability in the theory of computation.

Relations, Sequences, Summation CS-101: Advanced information, computation, communication I

Covers arithmetic progressions, lattices, formal verification, strings, explicit formulas, recurrence relations, closed formulas, and Cantor's Diagonal Argument.

Cantor's Diagonal Argument CS-101: Advanced information, computation, communication I

Explores Cantor's Diagonal Argument and the concept of uncountability through binary digit sequences.

Relations, Sequences and Summations CS-101: Advanced information, computation, communication I

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

Cartesian Product and Induction

Introduces Cartesian product and induction for proofs using integers and sets.

Socialist calculation debate

The socialist calculation debate, sometimes known as the economic calculation debate, was a discourse on the subject of how a socialist economy would perform economic calculation given the absence of the law of value, money, financial prices for capital goods and private ownership of the means of production. More specifically, the debate was centered on the application of economic planning for the allocation of the means of production as a substitute for capital markets and whether or not such an arrangement would be superior to capitalism in terms of efficiency and productivity.

Calculation in kind

NOTOC Calculation in kind or calculation in-natura is a way of valuating resources and a system of accounting that uses disaggregated physical magnitudes as opposed to a common unit of calculation. As the basis for a socialist economy, it was proposed to replace money and financial calculation. In an in-kind economy products are produced for their use values (their utility) and accounted in physical terms. By contrast, in money-based economies, commodities are produced for their exchange value and accounted in monetary terms.

Economic calculation problem

The economic calculation problem (sometimes abbreviated ECP) is a criticism of using economic planning as a substitute for market-based allocation of the factors of production. It was first proposed by Ludwig von Mises in his 1920 article "Economic Calculation in the Socialist Commonwealth" and later expanded upon by Friedrich Hayek. In his first article, Mises described the nature of the price system under capitalism and described how individual subjective values (while criticizing other theories of value) are translated into the objective information necessary for rational allocation of resources in society.

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.

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.