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
