Re: Turing computable function

sanchopancho80 wrote:
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?

Hmm, no. The confusion ultimately comes from this. A total function
f : X -> Y is defined at each point of X. On the other hand, a partial
function f : X -> Y is defined possibly at only some (or even no) points
of X. And then there are also things that aren't in the set X at all.
So there are really 3 cases.

An example, suppose:

f : N -> N
f(x) = sqrt(x/2)

(where N is the natural numbers.) Then f is defined only at natural
numbers that are twice some perfect square. But I've still given it a
nominal domain of N, so it's a partial function on N. Now, depending on
how you encode natural numbers on the input tape of your Turing machine,
there may be some possible input tapes that don't represent natural
numbers at all. For example, if your input alphabet is ASCII, then
suppose the input is "xy56.3#". That's not even in the nominal domain,
so whether f is defined there is sort of a malformed question.

So, in order to have the Turing machine compute f, we have to have:

On input ... TM outputs...
-----------------------------------------------
twice a perfect square sqrt(x/2)
some other natural MUST loop
something else ????

Clearly it must produce the right answer when it is defined, and it must
loop when you give it something it expects, but for which the function is
undefined. But the question is what the machine needs to do for
"something else". If you require that the TM loop in the "something
else" case, then you can recursively enumerate the graph language given a
machine to compute functions. But if not, and if the nominal domain is
itself not r.e., then you can't.

I'm not giving you an answer. Just explaining the distinction Matt was
making. I certainly believe that one should consider the nominal domain
for any (partial) function computed by a TM to be the set of all strings
over the input alphabet, which avoids the issue entirely. The only thing
you gain by doing otherwise is some sleight of hand that complicates the
matter. But I'm also not quite universal that everyone else will agree
with me, so Matt's caution is justified.

--
Chris Smith
.

Relevant Pages

  • Re: Turing computable function
    ... output tape and stop even if fisn't defined. ... definition of a partial function to be Turing computable? ... nominal domain of N, so it's a partial function on N.  Now, depending on ... So, in order to have the Turing machine compute f, we have to have: ...
    (comp.theory)
  • 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)