Return to Answer

Given $TM_L$ which acceps language $L$, let's construct $TM_{PL}$ to accept $Prefix(L)$.

Since the set of strings is countable, we can find an one-to-one mapping $f: N \to \Sigma^\star$ from natural numbers to all strings. So $TM_{PL}$ accepts $x$ iff there is an $i$ that $TM_L$ accepts $w(i) = x$ ## $f(i)$ (here ## means string concatenation). The intuitive idea to construct $TM_{PL}$ is to enumerate all $w(i)$ one by one and put $TM_L$ with input $w(i)$ to an universal turing machine $UTM$ to find whether $w(i) \in L$. But it fails to return the correct answer when $TM_{L}$ accepts $w(a)$ while it falls into an infinite loop in some $w(b)$ with $b < a$. Let's find how to avoid this situation.

Remember how to prove the conclusion that $N_+ \times N_+$ is countable, where $N_+$ is the set of all positive natural numbers. We can enumerate $(i, j)$ in the order $(1, 1) \to (2, 1) \to (1, 2) \to (3, 1) \to (2, 2) \to (1, 3) \ldots$. The same technique can be used to solve this problem, where pair $(i, j)$ means "Put $TM_L$ with input $w_i$ to $UTM$ and find whether $TM_L$ accepts $w_i$ in no greater than $j$ steps". The answer of each pair $(i, j)$ can be got in finite number of steps, and it's not hard to see that $x \in Preifx(L)$ iff there is a pair $(i, j)$ whose answer is yes.

Given $TM_L$ which acceps language $L$, let's construct $TM_{PL}$ to accept $Prefix(L)$.

Since the set of strings is countable, we can find an one-to-one mapping $f: N \to \Sigma^\star$ from natural numbers to all strings. So $TM_{PL}$ accepts $x$ iff there is an $i$ that $TM_L$ accepts $w(i) = x$ ## $f(i)$ (here ## means string concatenation). The intuitive idea to construct $TM_{PL}$ is to enumerate all $w(i)$ one by one and put $TM_L$ with input $w(i)$ to an universal turing machine $UTM$ to find whether $w(i) \in L$. But it fails to return the correct answer when $TM_{L}$ accepts $w(a)$ while it falls into an infinite loop in some $w(b)$ with $b < a$. Let's find how to avoid this situation.

Remember how to prove the conclusion that $N_+ \times N_+$ is countable, where $N_+$ is the set of all positive natural numbers. We can enumerate $(i, j)$ in the order $(1, 1) \to (2, 1) \to (1, 2) \to (3, 1) \to (2, 2) \to (1, 3) \ldots$. The same technique can be used to solve this problem, where pair $(i, j)$ means "Put $TM_L$ with input $w(i)$ to $UTM$ and find whether $TM_L$ accepts $w(i)$ in no greater than $j$ steps". The answer of each pair $(i, j)$ can be got in finite number of steps, and it's not hard to see that $x \in Prefix(L)$ iff there is a pair $(i, j)$ whose answer is yes.

Given $TM_L$ which acceps language $L$, let's construct $TM_{PL}$ to accept $Prefix(L)$.

Since the set of strings is countable, we can find an one-to-one mapping $f: N \to \Sigma^\star$ from natural numbers to all strings. So $TM_{PL}$ accepts $x$ iff there is an $i$ that $TM_L$ accepts $w(i) = x$ ## $f(i)$ (here ## means string concatenation). The intuitive idea to construct $TM_{PL}$ is to enumerate all $w(i)$ one by one and put $TM_L$ with input $w(i)$ to an universal turing machine $UTM$ to find whether $w(i) \in L$. But it fails to return the correct answer when $TM_{L}$ accepts $w(a)$ while it falls to an infinite loop in some $w(b)$ with $b < a$. Let's find how to avoid this situation.

Remember how to prove the conclusion that $N_+ \times N_+$ is countable, where $N_+$ is the set of all positive natural numbers. We can enumerate $(i, j)$ in the order $(1, 1) \to (2, 1) \to (1, 2) \to (3, 1) \to (2, 2) \to (1, 3) \ldots$. The same technique can be used to solve this problem, where pair $(i, j)$ means "Put $TM_L$ with input $w_i$ to $UTM$ and find whether $TM_L$ accepts $w_i$ in no greater than $j$ steps". The answer of each pair $(i, j)$ can be got in finite number of steps, and it's not hard to see that $x \in Preifx(L)$ iff there is a pair $(i, j)$ whose answer is yes.

Given $TM_L$ which acceps language $L$, let's construct $TM_{PL}$ to accept $Prefix(L)$.

Since the set of strings is countable, we can find an one-to-one mapping $f: N \to \Sigma^\star$ from natural numbers to all strings. So $TM_{PL}$ accepts $x$ iff there is an $i$ that $TM_L$ accepts $w(i) = x$ ## $f(i)$ (here ## means string concatenation). The intuitive idea to construct $TM_{PL}$ is to enumerate all $w(i)$ one by one and put $TM_L$ with input $w(i)$ to an universal turing machine $UTM$ to find whether $w(i) \in L$. But it fails to return the correct answer when $TM_{L}$ accepts $w(a)$ while it falls into an infinite loop in some $w(b)$ with $b < a$. Let's find how to avoid this situation.

Remember how to prove the conclusion that $N_+ \times N_+$ is countable, where $N_+$ is the set of all positive natural numbers. We can enumerate $(i, j)$ in the order $(1, 1) \to (2, 1) \to (1, 2) \to (3, 1) \to (2, 2) \to (1, 3) \ldots$. The same technique can be used to solve this problem, where pair $(i, j)$ means "Put $TM_L$ with input $w_i$ to $UTM$ and find whether $TM_L$ accepts $w_i$ in no greater than $j$ steps". The answer of each pair $(i, j)$ can be got in finite number of steps, and it's not hard to see that $x \in Preifx(L)$ iff there is a pair $(i, j)$ whose answer is yes.

Given $TM_L$ which acceps language $L$, let's construct $TM_{PL}$ to accept $Prefix(L)$.

Since the set of strings is countable, we can find an one-to-one mapping $f: N \to \Sigma^\star$ from natural number to all strings. So $TM_{PL}$ accepts $x$ iff there is an $i$ that $TM_L$ accepts $w(i) = x$ ## $f(i)$ (here ## means string concatenation). The intuitive idea to construct $TM_{PL}$ is to enumerate all $w(i)$ one by one and put $TM_L$ with input $w(i)$ to an universal turing machine $UTM$ to find whether $w(i) \in L$. But it fails to return the correct answer when $TM_{L}$ accepts $w(a)$ while it falls to an infinit loop in some $w(b)$ with $b < a$. Let's find how to avoid this situation.

Remember how to prove the conclusion that $N_+ \times N_+$ is countable, where $N_+$ is the set of all positive natural numbers. We can enumerate $(i, j)$ in the order $(1, 1) \to (2, 1) \to (1, 2) \to (3, 1) \to (2, 2) \to (1, 3) \ldots$. The same technique can be used to solve this problem, where pair $(i, j)$ means "Put $TM_L$ with input $w_i$ to $UTM$ and find whether $TM_L$ accepts $w_i$ in no greater than $j$ steps". The answer of each pair $(i, j)$ can be got in finite number of steps, and it's not hard to see that $x \in Preifx(L)$ iff there is a pair $(i, j)$ whose answer is yes.

Given $TM_L$ which acceps language $L$, let's construct $TM_{PL}$ to accept $Prefix(L)$.

Since the set of strings is countable, we can find an one-to-one mapping $f: N \to \Sigma^\star$ from natural numbers to all strings. So $TM_{PL}$ accepts $x$ iff there is an $i$ that $TM_L$ accepts $w(i) = x$ ## $f(i)$ (here ## means string concatenation). The intuitive idea to construct $TM_{PL}$ is to enumerate all $w(i)$ one by one and put $TM_L$ with input $w(i)$ to an universal turing machine $UTM$ to find whether $w(i) \in L$. But it fails to return the correct answer when $TM_{L}$ accepts $w(a)$ while it falls to an infinite loop in some $w(b)$ with $b < a$. Let's find how to avoid this situation.

Remember how to prove the conclusion that $N_+ \times N_+$ is countable, where $N_+$ is the set of all positive natural numbers. We can enumerate $(i, j)$ in the order $(1, 1) \to (2, 1) \to (1, 2) \to (3, 1) \to (2, 2) \to (1, 3) \ldots$. The same technique can be used to solve this problem, where pair $(i, j)$ means "Put $TM_L$ with input $w_i$ to $UTM$ and find whether $TM_L$ accepts $w_i$ in no greater than $j$ steps". The answer of each pair $(i, j)$ can be got in finite number of steps, and it's not hard to see that $x \in Preifx(L)$ iff there is a pair $(i, j)$ whose answer is yes.