Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!zaphod.mps.ohio-state.edu!magnus.acs.ohio-state.edu!tut.cis.ohio-state.edu!uoft02.utoledo.edu!desire.wright.edu!wright!econrad
From: econrad@cs.wright.edu (Eric Conrad)
Newsgroups: comp.theory.cell-automata
Subject: Re: How Intelligent are the Winning Ways?
Message-ID: <1991Mar13.095332.7152@cs.wright.edu>
Date: 13 Mar 91 09:53:32 GMT
References: <1991Mar12.155051.16488@zorch.SF-Bay.ORG>
Organization: Wright State University
Lines: 29

From article <1991Mar12.155051.16488@zorch.SF-Bay.ORG>, by xanthian@zorch.SF-Bay.ORG (Kent Paul Dolan):
> By which I should have clarified that I meant that in terms of the
> number of cycles needed to complete an operation, operations that have
> the same order statististics for a Turing machine have very different
> order statistics for the moving tape case in Life. Example: move right
> writing a symbol into each blank frame "forever", and doing that but
> pausing one "step" time at each frame are both order N time operations
> in the number N of frames traversed on a Turing machine. The first is
> still order N on a moving tape Life emulation of a Turing machine, but
> the second is (at least) order N*N, since the emulation has to wait for
> the cessession/resumption of motion to reach the (ever more distant)
> left end of the tape and report back between each pair of steps.

(1) Analysis of the time complexity of a TM implementation is in terms
of TM transitions.  No assumptions need to be made about the
underlying time complexity of individual transitions.

(2) If the analysis of Life transitions is correct, it would appear
that the Life simulation of a TM preserves polynomial time
complexity.  More specifically, if the time complexity of a Turing
machine measured in TM transitions is f(n), bounded above by
some polynomial P(n), then the complexity measured in Life transitions
is O(P(n^2)).
 
-- 
-- Eric Conrad - Wright State University

A great many people think they are thinking when they
are merely rearranging their prejudices.  -- William James