Lecture

Undecidability: Recursive Languages and Turing Machines

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 delves into the concept of undecidability, focusing on recursive languages, Turing machines, and the halting problem. The instructor explains how certain languages cannot be decided by a Turing machine, leading to the notion of indescribable problems. Through examples and proofs, the lecture demonstrates the complexity of determining the acceptance of languages by machines, ultimately showcasing the limitations of computation. The discussion also touches on the universal language of Turing machines and the implications of decidability and undecidability in computational theory.

Official source

Ontological neighbourhood

Theoretical computer science

Theory of computation: Computability theory, Computational complexity theory

Related concepts (32)

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

Turing machine

A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer algorithm. The machine operates on an infinite memory tape divided into discrete cells, each of which can hold a single symbol drawn from a finite set of symbols called the alphabet of the machine. It has a "head" that, at any point in the machine's operation, is positioned over one of these cells, and a "state" selected from a finite set of states.

Computational complexity theory

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm. A problem is regarded as inherently difficult if its solution requires significant resources, whatever the algorithm used.

Computational complexity

In computer science, the computational complexity or simply complexity of an algorithm is the amount of resources required to run it. Particular focus is given to computation time (generally measured by the number of needed elementary operations) and memory storage requirements. The complexity of a problem is the complexity of the best algorithms that allow solving the problem. The study of the complexity of explicitly given algorithms is called analysis of algorithms, while the study of the complexity of problems is called computational complexity theory.

Nondeterministic Turing machine

In theoretical computer science, a nondeterministic Turing machine (NTM) is a theoretical model of computation whose governing rules specify more than one possible action when in some given situations. That is, an NTM's next state is not completely determined by its action and the current symbol it sees, unlike a deterministic Turing machine. NTMs are sometimes used in thought experiments to examine the abilities and limits of computers.

Related lectures (64)

Turing Machines: Recursive Languages

Covers Turing machines, recursive languages, undecidability, and infinite executions in computational theory.

Recursive Enumerability: Turing Machines and Undecidable Languages

Covers recursively enumerable languages, Turing machines, and the construction of undecidable languages.

Turing Machines: Recursive Languages

Explores Turing machines, recursive languages, and decidability in the theory of computation.

Turing Machines: Recursive Languages

Explores Turing machines, recursive languages, undecidability, and symbol elimination.

Theory of Computation: Undecidable Problems

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

Related concepts (32)

Undecidable problem

Turing machine

Computational complexity theory

Computational complexity

Nondeterministic Turing machine