tag

#undecidability

4 pages tagged

Maths › 03. Logic and Foundations ›

24. Limits of Formal Systems

Limits of formal systems study the boundaries of what can be proved, computed, and expressed within precise mathematical frameworks, and they show that even very strong systems have inherent restrictions that cannot be removed by technical refinement alone. The chapter begins with incompleteness, where certain true statements cannot be derived from a given formal system, provided that the system is sufficiently expressive and consistent, and this reveals a gap between...
logic foundations incompleteness undecidability independence May 2, 2026
Maths › 03. Logic and Foundations ›

11.5 Undecidability Results

11.5 Undecidability Results The halting problem is the first major example of an undecidable problem. Once we know that one problem is undecidable, we can use it to prove that many other problems are undecidable too. A decision problem asks for a yes-or-no answer. In computability theory, we usually represent a decision problem as a language: $$ L \subseteq \Sigma^* $$ A machine decides $L$ if it always halts and...
undecidability reductions rice theorem computability logic May 2, 2026
Maths › 03. Logic and Foundations ›

11.4 Halting Problem

11.4 Halting Problem The halting problem asks whether a Turing machine eventually stops. Given a machine $M$ and an input word $w$, we ask: $$ \text{Does } M \text{ halt on input } w? $$ Here “halt” means that the computation eventually reaches a stopping state, such as: $$ q_{\mathrm{accept}} $$ or: $$ q_{\mathrm{reject}} $$ If $M$ reaches one of these states after finitely many steps, then $M$ halts on...
halting problem undecidability computability logic theory May 2, 2026
Maths › 03. Logic and Foundations ›

11. Turing Machines

Turing machines provide a simple formal model of computation, where an algorithm is represented by a finite set of instructions acting on a tape, a head position, and an internal state. The chapter begins with machine definitions, including the tape alphabet, states, transition function, starting configuration, accepting and rejecting states, and the precise meaning of one step of computation. Computation traces are then introduced to describe the full sequence of...
logic computability turing machines undecidability May 2, 2026