tag

#theory

2 pages tagged

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

Maths › 03. Logic and Foundations ›

11.1 Machine Definitions

11.1 Machine Definitions A Turing machine is a formal model of an algorithm. It describes computation using a finite set of rules and an unbounded tape. The machine has three main parts: Part Role Tape stores symbols Head reads and writes one cell at a time Finite control stores the current state The tape is divided into cells: $$ \cdots,\ c_{-2},\ c_{-1},\ c_0,\ c_1,\ c_2,\ \cdots $$ Each cell contains...