tag

#halting problem

2 pages tagged

Maths › 03. Logic and Foundations ›

12.3 Recursively Enumerable Sets

12.3 Recursively Enumerable Sets A set is recursively enumerable if there is an algorithm that can list its elements. The older name is recursively enumerable , often abbreviated as r.e. The modern name is computably enumerable , often abbreviated as c.e. Both terms refer to the same idea. A set $A \subseteq \mathbb{N}$ is recursively enumerable if there is a Turing machine that prints exactly the elements of $A$: $$...

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