# Show that Halting problem $(\mathsf{HP\text{}})$ is $\mathsf{NP\text{-}Hard}$

Let me define first Halting problem $(\mathsf{HP\text{}})$.

Given : $(M , x)$, $M$ is a turing machine and $x$ is a input binary string to turing machine $M$.

Decide : Does $M$ halt on string $x$?

I tried to reduce $\mathsf{SAT\text{}}$ instance to $\mathsf{HP\text{}}$ in polynomial time. Let $\phi$ be a instance of $\mathsf{SAT\text{}}$ and define a map $\mathsf{T\text{}} \colon \mathbb \phi \to\mathbb M$. If $\phi$ is satisfiable (means true) then turing machine $M$ will halt on string $x$ and if $\phi$ is not satisfiable (means false) then turing machine $M$ will not halt on string $x$.

I don't know whether the map $\mathsf{T\text{}}$ right or wrong. So my question is how to define a map and to compute this map in polynomial time?

Given a SAT formula $\varphi$, construct a Turing machine which iterates over all truth assignments for $\varphi$, and so determines if $\varphi$ is satisfiable or not. If it is, it halts. If it isn't, it doesn't halt (gets into an infinite loop).
NP is the "length- and time-bounded" version of the halting problem, or rather, of $\Sigma_1$. The class $\Sigma_1$ consists of all predicates $P$ such that $$P(x) \leftrightarrow \exists y \, \Pi(x,y),$$ where $\Pi$ is a computable predicate. NP is defined in a very similar way, by adding two restrictions:
1. $y$ has to be polynomially bounded (in $x$).
2. $\Pi$ has to be computable in polynomial time.