Prev: Call for Papers Reminder (extended): The World Congress on Engineering WCE 2010
Next: ICNAAM 2010 Mini-Symposium on Computational Bioimaging and Visualization
From: Bernd L on 9 Mar 2010 12:46
Is it true that given Turing computable function f, there exists a
uniform family of circuits {Cn} that computes f? If this is true, how
are the output of the Turing machine and the output bits of the
circuits Cn related? Is there a standard reference where I can find
out more about this?
From: RussellE on 9 Mar 2010 23:00
On Mar 9, 9:46 am, Bernd L <berndlos...(a)gmail.com> wrote:
> Is it true that given Turing computable function f, there exists a
> uniform family of circuits {Cn} that computes f?

Yes, if the input and output are finite.

> If this is true, how
> are the output of the Turing machine and the output bits of the
> circuits Cn related?

The output bits can represent a position on the output tape
of the TM. If a certain position is '1' on the output tape for
a given input, the input tape becomes a clause in the circuit
for that position.

> Is there a standard reference where I can find
> out more about this?

From: Bernd L on 10 Mar 2010 16:49
> > Is it true that given Turing computable function f, there exists a
> > uniform family of circuits {Cn} that computes f?
>
> Yes, if the input and output are finite.

How do you deal with the case when the input and/or output are
infinite?


From: RussellE on 11 Mar 2010 16:12
On Mar 10, 1:49 pm, Bernd L <berndlos...(a)gmail.com> wrote:
> > > Is it true that given Turing computable function f, there exists a
> > > uniform family of circuits {Cn} that computes f?
>
> > Yes, if the input and output are finite.
>
> How do you deal with the case when the input and/or output are
> infinite?

I would not be the best person to ask about infinity.
If the input/output is infinite, the circuit will need
an infinite number of input/output bits.

I wouldn't consider a function with infinite input/output
to be Turing computable.


Russell
- Integers are an illusion
From: Torben �gidius Mogensen on 12 Mar 2010 04:00
Bernd L <berndlosert(a)gmail.com> writes:

>> > Is it true that given Turing computable function f, there exists a
>> > uniform family of circuits {Cn} that computes f?
>>
>> Yes, if the input and output are finite.
>
> How do you deal with the case when the input and/or output are
> infinite?

Turing machines do not deal with infinite input and output.

The tape is unbounded, but the input is only allowed to use a finite
portion and you only say that a function is Turing computable if a
Turing machine can compute it in a finite number of steps, which
precludes infinite output.

You can, however, talk about online Turing machines, which are TMs where
not all the input is given at the start. Here, some input is given, the
machine runs for a while and outputs some output, gets some more input
and so on. It is possible for an online TM to have infinite input, but
it will only read a finite part and run a finite time before outputting
some part of the output.

Torben
 | 
Pages: 1
Prev: Call for Papers Reminder (extended): The World Congress on Engineering WCE 2010
Next: ICNAAM 2010 Mini-Symposium on Computational Bioimaging and Visualization