Author: Robert Hyatt
Date: 10:40:44 10/11/01
Go up one level in this thread
On October 10, 2001 at 20:57:10, Dave Gomboc wrote: >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 I think that is usually covered under "Cook's theorem" but I gave some easier to understand citings from several books on parallel programming that discuss "super-linear speedup" specifically rather than some tough-to-read mathematical proofs of why all Turing machine types are essentially equal in power. I also gave a citation for a short paper that directly and concisely discusses the issue and shows why such is impossible in anything other than an exceptional case, not an average performance...
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.