Show that if $L$ is recursively enumerable (RE) then $L$ is the domain of some partial computable function

429 Views Asked by At

Show that if $L$ is recursively enumerable (RE) then $L$ is the domain of some partial computable function

I know that what it does mean recursively enumerable, but I don't what it does mean domain of some partial computable function.
So, not only I can't prove it, I even don't know what to prove.
I tried to solve similar tasks, but no effect.

Can you help me, please? I ask for explanation for dummy.

Edit

So, lets try to construct function $f: L\to \{0,1\}$ where

$$f(w \not \in L) = 0 \text{iff Turing machine rejects $w$} f(w\in L) = 1 \text{iff Turing machine accepts $w$}$$

it should ends proof.

1

There are 1 best solutions below

7
On

Fix some algorithm (Turing machine/computer program in some Turing-complete language...). For any given input, the algorithm can:

(a) Run for some finite time and give a result.

OR

(b) Run forever.

This gives a partial computable function: is defined and computable for some inputs (case a) and undefined for other inputs (case b).

EDIT:

Let be $A$ the algorithm than enumerates the members of $L$. We can define another algorithm by "running $A$ in parallel":

Do the first step of $A(1)$;

Do the second step of $A(1)$;

Do the first step of $A(2)$;

Do the third step of $A(1)$;

Do the second step of $A(2)$;

Do the first step of $A(3)$;

$\cdots$

If $A(n)$ stops, define $f(n) = 1$. If $A(n)$ runs forever, $f(n)$ is undefined.