Recursively enumerable sets are domain of partial recursive functions

359 Views Asked by At

My definition of recursively enumerable set is that it is the language recognized by some Turing machine.

I want to show that this definition is equivalent to "a r.e. set is the domain of some recursive function". I managed to show that the later implies the former but I have some troubles with the other direction. I just don't see how to start.

1

There are 1 best solutions below

0
On BEST ANSWER

Hint: what function is computed by a Turing machine that recognises an r.e. set?