PadhaikoAll subjects

Past exam question: 2081 Chaitra (Regular), Q1(a)(i)

Theory of Computation · 1 marks

Open in the Padhaiko app

Topic: Induction, Diagonalization & Pigeonhole Principle

Question

State Diagonalization principle.

Solution

Cantor's Diagonalization Principle: The Diagonalization Principle (introduced by Georg Cantor in 1891) is a mathematical proof technique used to demonstrate that certain infinite sets cannot be enumerated (are uncountable), or that certain computational problems cannot be solved by any Turing machine (are undecidable).

Principle: Given an infinite list of sequences or functions where , one constructs a new sequence whose -th element differs from the diagonal element of the list (e.g., ):

Because differs from the -th sequence in at least the -th position for every , cannot appear anywhere in the enumerated list, proving that the collection is inherently unlistable (uncountable).

Significance in TOC: Used directly to prove the uncountability of real numbers and the undecidability of the Halting Problem ( and ).

Answer:

The Diagonalization Principle proves uncountability or undecidability by showing that any proposed enumeration of objects can be refuted by constructing a diagonal object that differs from the -th object at position (), guaranteeing is missing from the list.

All past exam questions for Theory of Computation