7
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ for simplicity assume you are programmer and you wrote a program with while loop, but you forget to write a correct termination for your loop, could you write a general program which works for all possible inputs (programs), and says they will terminate or not? for example this are infinite: while(true); while(i<i+1); while (n<k){k++;},...., could you write one program to check whether all possible programs with all possible inputs are terminating? and in Turing machine sense means all possible words for all of them. $\endgroup$
    – user742
    Feb 12, 2013 at 10:18
  • $\begingroup$ It is a very simple and cool animation describes Turing Halting problem in real software engineering practice: The Halting Problem - Part 1 The Halting Problem - Part 2 There is also other lecture that might be useful: Lecture 13 - The Halting Problem $\endgroup$
    – Reza
    Feb 12, 2013 at 22:28

3 Answers 3

Reset to default
5
$\begingroup$

The set (or language if you will) $H_{TM}$ is a set of pairs $(M,w)$ where $w$ is any string of your alphabet and $M$ is a Turing machine, and $M$ halts with $w$ as input.

This means that a pair $P = (M,w)$ is in the set $H_{TM}$ if and only if $M(w) \downarrow$.

Deciding this set is however not possible. There is no Turing machine that accepts this language and nothing more. This is a version of the halting problem (hence the $H$).

Improve this answer
$\endgroup$
5
$\begingroup$

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

Improve this answer
$\endgroup$
1
$\begingroup$

here is a simple/informal definition of the halting problem with minimal symbolic/mathematical language. first, consider the Turing machine. Turing machines solve different problems based on (programming via) their state table.

now, the state table of any Turing machine itself can be encoded as a string, just like any inputs to a Turing machine. now consider a hypothetical machine ${TM}_H$ which accepts an encoding pair of a state table of a machine $M$, and an input string $w$: $\langle M, w \rangle$. suppose this $TM_H$ accepts the input iff (if and only if) machine $M$ halts on input $w$. by Turing's famous halting problem proof (1936), ${TM}_H$ cannot exist, ie this "problem" is uncomputable.

the $H_{TM}$ you describe is the description of this same problem in terms of set/language membership. a string is in the set $H_{TM}$ iff $M$ halts on $w$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.