Author: Dave Gomboc
Date: 17:57:10 10/10/01
Go up one level in this thread
On October 10, 2001 at 17:12:37, Miguel A. Ballicora wrote: >On October 08, 2001 at 14:59:12, Robert Hyatt wrote: > >>On October 08, 2001 at 13:52:56, Olaf Jenkner wrote: >> >>>I'm mathemathician. I believe that every student of informatics learnt something >>>about this topic. Maybe we can construct a turing machine to prove the >>>impossibilaty of SS. Is this the case? If it is, why does Dr. Hyatt waste his >>>time to convince people about it? >>> >>>OJe >> >> >>Simply because I have become a "teacher" over the past 31 years of my life >>as a university faculty member. And such "myths" need to be corrected when >>they show up, else they become self-propogating 'truths' that are anything >>but that... >> >>I have given the simple approach to proving this that is given in most every >>book I have seen (the time-slicing approach). I have referenced the formal >>proof in theory books that show "A two-tape (which is really a two-instruction >>stream) Turing machine has no more computational power than a one-tape (one >>instruction stream) computer." I have taken _every_ suggested algorithm that > >I am going to be a good boy and go to the library that is few blocks from here >(I have to go anyway). >Can you give the exact reference so I can read that theorem? If possible, >the name of the theorem or much better the name of a book and page number. >I think I should be able to find it. > >Regards, >Miguel Most introductory books on Computational Complexity should have an adequate discussion of universal turing machines. One I know of by Papadimitriou is called just that, "Computational Complexity". Dave
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.