<p>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$.</p>

<p>For forcing, there are many resources, depends on what you want to learn. A point to start is the Wikipedia pages and the references listed there: <a href="http://en.wikipedia.org/wiki/Forcing_%28set_theory%29" rel="nofollow">Forcing (set theory)</a>, <a href="http://en.wikipedia.org/wiki/Forcing_%28recursion_theory%29" rel="nofollow">Forcing (recursion theory)</a>. Timothy Chow's article <a href="http://arxiv.org/abs/0712.1320" rel="nofollow">A Beginner's Guide to Forcing</a> is a good introduction.</p>

CC BY-SA 3.0
2013-04-03T14:13:06.623Z
While the links are relevant, they certainly do not give enough information to complete the proof outlined by Bjorn. In particular the page on Forcing and recursion theory is atrocious.
cody
CC BY-SA 3.0
2013-04-03T14:45:33.443Z
@cody, that question was added after my answer. I answered what was originally asked. And I am not sure it is a good idea to give an introduction to forcing here when Tim has already written a very good and readable introduction to it. As I see it the OP in place of reading the easy to read reference he asked for wants us to explain it even simpler. Feel free to do so, but I am not sure I will.
Kaveh
CC BY-SA 3.0
2013-04-03T15:24:36.337Z
I really like Tim's introduction! However he makes no no mention of 1-genericity or give any mention to computability, which is what I meant by "not enough information to complete the proof outline".
cody
CC BY-SA 3.0
2013-04-03T16:36:31.667Z
@cody, OK, I will try to address that (I don't have much free time right now, and I am hoping that Tim himself or someone else (Josh, Andrej, Emil, ...)  will answer it before I find time :).
Kaveh
CC BY-SA 3.0
2013-04-03T18:49:34.053Z
Thanks! I'll admit that I am interested in the answer to this question as well.
cody
CC BY-SA 3.0
2013-03-02T07:54:20.720Z
2013-03-02T07:54:20.720Z
Kaveh
<p>This question is about an answer in question </p>

<blockquote>
  <p><a href="https://cstheory.stackexchange.com/questions/2853/are-there-any-proofs-the-undecidability-of-the-halting-problem-that-does-not-dep">Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization ?</a></p>
</blockquote>

<p><a href="https://cstheory.stackexchange.com/a/2854/">Bjørn Kjos-Hanssen answer</a> states that:</p>

<blockquote>
  <p>You can first show that the halting problem (the set $0'$) can be used
  to compute a set $G\subseteq\mathbb N$ that is <em>1-generic</em> 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).</p>
</blockquote>

<p>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.)</p>

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

<p>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?</p>

CC BY-SA 3.0
2013-03-02T08:02:13.633Z
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
<lo.logic><computability><proofs><halting-problem>
Explanation of 1-generic to prove undecidability of halting problem
user14000
# Explanation of 1-generic to prove undecidability of halting problem

(Asked by: username_0 on 2013-03-02)

This question is about an answer in question

> [Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization ?](https://cstheory.stackexchange.com/questions/2853/are-there-any-proofs-the-undecidability-of-the-halting-problem-that-does-not-dep)

[Bjørn Kjos-Hanssen answer](https://cstheory.stackexchange.com/a/2854/) states that:

> 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?

**Tags:** lo.logic, computability, proofs, halting-problem
> **Comments:**
> **username_1**: I edited the question to make it more interesting. I hope that I kept the original intention. Feel free to roll back or edit.  

---

## 1 answers

### Answer by username_1 on 2013-03-02. Score: 2

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

For forcing, there are many resources, depends on what you want to learn. A point to start is the Wikipedia pages and the references listed there: [Forcing (set theory)](http://en.wikipedia.org/wiki/Forcing_%28set_theory%29), [Forcing (recursion theory)](http://en.wikipedia.org/wiki/Forcing_%28recursion_theory%29). Timothy Chow's article [A Beginner's Guide to Forcing](http://arxiv.org/abs/0712.1320) is a good introduction.

> **Comments:**
> **username_2**: While the links are relevant, they certainly do not give enough information to complete the proof outlined by Bjorn. In particular the page on Forcing and recursion theory is atrocious.  
> **username_1**: @cody, that question was added after my answer. I answered what was originally asked. And I am not sure it is a good idea to give an introduction to forcing here when Tim has already written a very good and readable introduction to it. As I see it the OP in place of reading the easy to read reference he asked for wants us to explain it even simpler. Feel free to do so, but I am not sure I will.  
> **username_2**: I really like Tim's introduction! However he makes no no mention of 1-genericity or give any mention to computability, which is what I meant by "not enough information to complete the proof outline".  
> **username_1**: @cody, OK, I will try to address that (I don't have much free time right now, and I am hoping that Tim himself or someone else (Josh, Andrej, Emil, ...)  will answer it before I find time :).  
> **username_2**: Thanks! I'll admit that I am interested in the answer to this question as well.  

---

