Re: Turing computable function

Thank you for your answer.

On 12 Jul., 04:53, matt.timmerm...@xxxxxxxxx wrote:
On Jul 11, 5:13 pm, sanchopanch...@xxxxxx wrote:

Is a partial function X - - f - -> Y Turing computable iff its graph,
i.e. the set
L_f={(x,y)|y=f(x)}
is recursively enumerable?

A partial function is certainly computable if it's graph is r.e.  An
implementation of f(x) can just enumerate L_f until it finds an (x,y),
and then output y.

Ok, this is now clear to me.

Whether or not the converse is true depends on the precise definition
of "computable partial function" that you're using.  If you require
the implementation T to halt only if f(x,y) is defined, then you can
enumerate all inputs while simultaneously emulating T on all
previously enumerated inputs, producing each emulation's (x,y) when
x's emulation halts.

If you allow any definition at all for X, however, and you don't care
what T does for inputs that aren't in X, then X may not be r.e, and
the subset of X on which f(x) is defined may not be r.e., in which
case L_f is also not r.e, because an algorithm for enumerating L_f
could easily be adapted to enumerate that susbset.

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?

Again, I would be very glad if anybody could help me.

Thanks,
Sancho
.

Relevant Pages

  • Re: Turing computable function
    ... A partial function is certainly computable if it's graph is r.e. ... implementation of fcan just enumerate L_f until it finds an, ... Whether or not the converse is true depends on the precise definition ... x's emulation halts. ...
    (comp.theory)
  • Re: Setting (thread) priority of DirectShow Graphs/Filters ?
    ... pause the graph ... enumerate all the threads in the graph ... subract the orginal list and uprate the remaining thread priorities ... enumerate and pause. ...
    (microsoft.public.win32.programmer.directx.video)
  • Build BDA Graph - Enum tuners
    ... Then I create the reciever component by enumerate ... create a graph with the Technotrend device the tuner device is ok but when I ... Am I doing this the wrong way or is there a bug in some of the filters? ...
    (microsoft.public.win32.programmer.directx.video)
  • Re: Graph spy
    ... you can enumerate all the filters in the graph ... for each pin, identify the direction and connected to pin ... Which provides you with the nodes of a directed graph that you can do what ...
    (microsoft.public.win32.programmer.directx.video)
  • find all directed paths between a source and destination
    ... I have a graph of a ... I'm trying to enumerate through all directed paths ... shouldn't be an infinite number of solutions to this problem because ...
    (comp.theory)