Re: Turing computable function

Thank you for your detailed answer. Anyway, some questions remains.

On 12 Jul., 14:42, Chris Smith <cdsm...@xxxxxxxxx> wrote:
sanchopancho80 wrote:
My definition of a "computable partial function" is the following: A
partial function X - - f - -> Y is called "computable partial function"
iff there is a Turing machine T with an input and with an output tape
such that if you write an element x of X on the input tape,  the Turing
machine
- either writes f(x) on the output tape or - stops without writing
anything or doesn't stop.

This means in particular that I don't consider inputs which aren't in X..
Hence it should be equivalent to say that the graph of a partial
recursive function is r.e. or that f is a "computable partial function",
right?

No.

The issue that Matt is referring to is this.  From what you've written,
your Turing machine that computes f has a specific defined behavior only
when the input tape is in X.  So if the Turing machine produces output y
for some input tape x, then either:

(a) f(x) = y, OR
(b) x is not in X.

But in order to enumerate L = { (x,y) | y = f(x) }, you need to produce
an (x,y) pair only in case (a).  The two cases are indistinguishable, in
general.  If the set X is r.e., or if you require that the machine that
computes f should loop if its input is not in X, then you don't have this
problem.

If I have understood you in the correct way, a Turing machine which
computes f is allowed (for an input x of X) to write something on the
output tape and stop even if f(x) isn't defined. Is this the usual
definition of a partial function to be Turing computable? If it is,
can you give me a reference for that, please?

My definition of a partial function X - - f - ->Y function to be
Turing computable is that there is a Turing machine T with an input
and an output tape such that for any x of X on the input tape of T
there are only three possibilities of behavior of T
(1) T halts and writes exactly f(x) on the output tape
(2) T does not halt and writes anything on the output tape
(3) T halts and writes nothing on the output tape
and (1) happens iff x is f is defined at x and (2) or (3) happens iff
f isn't defined at x.

With this definition I don't see any problems for the graph not being
recursive enumerable!

Thanks,
S.
.