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

Lecture

Turing Machines: Decidability and Recursion Theory

Description

This lecture covers the concept of decidability in the context of Turing machines, exploring the Church-Turing thesis, undecidability, recursive languages, and the content of the tape at the end of computation.

Official source

Ontological neighbourhood

Theoretical computer science

Theory of computation: Computability theory

Related concepts (26)

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.

Decidability (logic)

In logic, a true/false decision problem is decidable if there exists an effective method for deriving the correct answer. Zeroth-order logic (propositional logic) is decidable, whereas first-order and higher-order logic are not. Logical systems are decidable if membership in their set of logically valid formulas (or theorems) can be effectively determined. A theory (set of sentences closed under logical consequence) in a fixed logical system is decidable if there is an effective method for determining whether arbitrary formulas are included in the theory.

Recursive language

In mathematics, logic and computer science, a formal language (a set of finite sequences of symbols taken from a fixed alphabet) is called recursive if it is a recursive subset of the set of all possible finite sequences over the alphabet of the language. Equivalently, a formal language is recursive if there exists a Turing machine that, when given a finite sequence of symbols as input, always halts and accepts it if it belongs to the language and halts and rejects it otherwise.

Decider (Turing machine)

In computability theory, a decider is a Turing machine that halts for every input. A decider is also called a total Turing machine as it represents a total function. Because it always halts, such a machine is able to decide whether a given string is a member of a formal language. The class of languages which can be decided by such machines is the set of recursive languages. Given an arbitrary Turing machine, determining whether it is a decider is an undecidable problem.

Church–Turing thesis

In computability theory, the Church–Turing thesis (also known as computability thesis, the Turing–Church thesis, the Church–Turing conjecture, Church's thesis, Church's conjecture, and Turing's thesis) is a thesis about the nature of computable functions. It states that a function on the natural numbers can be calculated by an effective method if and only if it is computable by a Turing machine. The thesis is named after American mathematician Alonzo Church and the British mathematician Alan Turing.

Related lectures (24)

Undecidability: Part 1

Introduces undecidability in recursive languages and Turing machines, showing languages without algorithmic recognition.

Turing Machines: Recursive Languages

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

Turing Machines: Recursive Languages

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

Undecidability: Recursive Languages and Turing Machines

Explores undecidability through recursive languages, Turing machines, and the halting problem.

Turing Machines: Recursive Languages

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

Related concepts (26)

Turing machine

Decidability (logic)

Recursive language

Decider (Turing machine)

Church–Turing thesis