# Explanation of 1-generic to prove undecidability of halting problem

Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization ?

You can first show that the halting problem (the set $0'$) can be used to compute a set $G\subseteq\mathbb N$ that is 1-generic meaning that in a sense each $\Sigma^0_1$ fact about $G$ is decided by a finite prefix of $G$. Then it is easy to prove that such a set $G$ cannot be computable (i.e., decidable).

I have trouble understanding this sentence as I am new to forcing. For example, what does "finite prefix" mean here? Can someone explain this sentence? (I know what $\Sigma^0_1$ means.)

Can someone explain the general idea behind forcing? I am also looking for easy to read introductions articles and books about forcing.

edit: So, how can we prove that each $\Sigma_1^0$ fact about $G$ being decided by a finite prefix leads to the fact that $G$ cannot be computable?

• I edited the question to make it more interesting. I hope that I kept the original intention. Feel free to roll back or edit. – Kaveh Mar 2 '13 at 8:02

A finite prefix of $G$ is $G \cap \{0,1,\ldots n\}$ for some $n$. It is easier if you look at the characteristic function of $G$ which can we viewed as an infinite word in $2^\omega$. Then a finite prefix is a finite initial part of $G$.