Return to Answer

The program $H$ which computes the function $$h(P,x)=\begin{cases} 1 & \text{If program $P$ will terminate on input $x$}\\ 0 & \text{otherwise} \end{cases}$$

This function (and the program that computes it) forms the basis of the most common proof of the impossibility of a solution solving the Halting Problem..

Thus it forms the basis of many proofs of in-computability, by showing that if some function $g$ (computed by a Program $G$), then $g$ would have the properties of $h$ and thus the would not be computable (and thus $G$ does not exist)

The program $H$ which computes the function $$h(P,x)=\begin{cases} 1 & \text{If program $P$ will terminate on input $x$}\\ 0 & \text{otherwise} \end{cases}$$

This function (and the program that computes it) forms the basis of the most common proof of the impossibility of a solution solving the Halting Problem..

Thus it forms the basis of many proofs of in-computability, by showing that if some function $g$ (computed by a Program $G$), then $g$ would have the properties of $h$ and thus the would not be computable (and thus $G$ does not exist)

These impossible programs are known as "halting oracles"; in fact, there's a whole hierarchy of them! h above only solves the program halting-problem. Since the oracle can't be a program, it can't solve its own halting problem. We can define an oracle h2 to solve the program-halting-oracle-halting-problem, but then we need another oracle h3 to solve the program-halting-oracle-halting-oracle-halting-problem, and so on.

The function $$h(P,x)=\begin{cases} 1 & \text{If program $P$ will terminate on input $x$}\\ 0 & \text{otherwise} \end{cases}$$

This function forms the basis of the most common proof of the impossibility of a solution solving the Halting Problem..

Thus it forms the basis of many proofs of in-computability, by showing that such if a function was computable, it would have the proper

The program $H$ which computes the function $$h(P,x)=\begin{cases} 1 & \text{If program $P$ will terminate on input $x$}\\ 0 & \text{otherwise} \end{cases}$$

This function (and the program that computes it) forms the basis of the most common proof of the impossibility of a solution solving the Halting Problem..

Thus it forms the basis of many proofs of in-computability, by showing that if some function $g$ (computed by a Program $G$), then $g$ would have the properties of $h$ and thus the would not be computable (and thus $G$ does not exist)

The function $$h(P,x)=\begin{cases} 1 & If\, program P\, will\, terminate\, on\, input\, x\\ 0 & otherwise \end{cases}$$

This function forms the basis of the most common proof of the impossibility of a solution solving the Halting Problem..

Thus it forms the basis of many proofs of in-computability, by showing that such if a function was computable, it would have the proper

The function $$h(P,x)=\begin{cases} 1 & \text{If program $P$ will terminate on input $x$}\\ 0 & \text{otherwise} \end{cases}$$

This function forms the basis of the most common proof of the impossibility of a solution solving the Halting Problem..

Thus it forms the basis of many proofs of in-computability, by showing that such if a function was computable, it would have the proper