Lukas' Notes

Not Every Decision Problem is decidable

May 01, 20261 min read

A decision problem P=⟨D,Y⟩ with a language L[P,enc] over a finite alphabet Σ can be identified with a function f:Σ∗→{0,1}, where 0 means NO and 1 means YES:

f:w↦{10​if w∈Yotherwise​

Since Σ∗ is countable, the set of all functions Σ∗→{0,1} is uncountable. Every algorithm has a finite description and is therefore countable. Hence, there are strictly more decision problems than algorithms, and most decision problems are not decidable.


Graph View

Backlinks

  • Decision Problem

Created with Quartz v4.4.0 © 2026

  • GitHub