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 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 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 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