World's most popular travel blog for travel bloggers.

[Solved]: Meaning of the Halting problem

, , No Comments
Problem Detail: 

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

Asked By : user6836

Answered By : Pål GD

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9699

0 comments:

Post a Comment

Let us know your responses and feedback