HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Meaning of the Halting problem

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
meaningthehaltingproblem

Problem

The Halting Problem is defined as:

$H_{TM} = \{ \langle M, w \rangle \mid \text{\(M\) halts on input \(w\)}\}$

I'm not sure what it means. Is $H_{TM}$ a collection of Turing Machines such that all of them accept/reject the word $w$? Is that a specific word? Or does that mean any word in their alphabet?

Thanks

Solution

We first choose an alphabet of symbols that our Turing machines can read and write on the tapes. Typically we have three symbols: $0$, $1$, and "empty". A word is a finite sequence of symbols.

If $u$ and $v$ are words we can form a new word $\langle u, v \rangle$ which represents the two words put together (this requires some coding so that we can tell where one words stops and the other begins).

A Turing machine can be be described by a word.

Like in all decidability problems, $H_{TM}$ is a set of words. More precisely, $H_{TM}$ contains all those words of the form $\langle M,w \rangle$ where $M$ is a Turing machine, $w$ is any word, and $M$ halts when we run it with input $w$.

Context

StackExchange Computer Science Q#9699, answer score: 5

Revisions (0)

No revisions yet.