Re: Turing computable function

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.

This is *not* a really interesting problem; it's a technical detail...
your definition of computing a function, as written, allows you to cheat
and hide away some difficulty, by specifying a smaller (and non-r.e.)
domain of discourse. My bias is that you should just avoid this problem
by considering only (partial) functions f : X -> Y where X is the entire
set of strings over the input alphabet. Then X is trivially r.e., and
you are fine. This is equivalent to allowing arbitrary X, but saying
that a TM that computes f must loop when it's input is not in X.

--
Chris Smith
.

Relevant Pages

  • Re: [QUIZ] The Turing Machine (#162)
    ... tape = tape ... The Turing Machine ... The three rules of Ruby Quiz 2: ... An infinite tape of memory cells that can hold one character ...
    (comp.lang.ruby)
  • Re: Symbol Grounding Problem
    ... on the tape before execution begins. ... But Windows is interactive, ... can a Turing machine run windows? ... PC can run the equivalent of an oracle, ...
    (comp.ai.philosophy)
  • Re: Turing machines, quantum computers, and alephs
    ... > number of tape segments, but if it starts with a blank tape, or a tape ... > the abstract quantum computer with infinitely many qubits might start ... > it seems no less finite in your sense than the abstract Turing machine ... > with its infinite but mostly zeroed tape. ...
    (comp.programming)
  • Re: Turing machines, quantum computers, and alephs
    ... > number of tape segments, but if it starts with a blank tape, or a tape ... > the abstract quantum computer with infinitely many qubits might start ... > it seems no less finite in your sense than the abstract Turing machine ... > with its infinite but mostly zeroed tape. ...
    (sci.math)
  • Re: [QUIZ] The Turing Machine (#162)
    ... This week's task is to build a Turing Machine, ... An infinite tape of memory cells that can hold one character ... head of the tape. ...
    (comp.lang.ruby)