![](/i/fill.gif) |
![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Am 04.01.2011 23:48, schrieb Darren New:
> clipka wrote:
>> And that's no problem, because CA are allowed to have that /by
>> definition/.
>
> That right there is what I'm asking about. I've never seen a definition
> that allows for a CA to have an infinite initialization other than to a
> default state. Do you have a citation to a definition that describes
> this? I am having trouble coming up with a trivial way to define what
> would be the allowable initialization and what would be the disallowed
> initialization without making reference to something outside the realm
> of CAs. Perhaps if you can describe its state based on a RE function of
> its index or something?
"An initial state (time t=0) is selected by assigning a state for each
cell."
(Wikipedia)
Isn't that plain enough? You assign a state for /each/ cell. CA's don't
seem to make any limitations on this.
Just like you "create" a TM [tape] to be initially empty except for a
limited section, you "create" a CA with an explicit initial state for
/each/ cell. How you pick that state per cell is purely a CA design
decision, and it doesn't matter whether you fetch that state out of thin
air already providing (part of) your solution. Just name /any/ rule for
that pattern - I guess the only limitation is that if you define the
initial state at time t=0 as a function of any states at time t>0 you
have a CA with oracle - and in fact may find yourself running straight
into a paradoxon.
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
On 22/12/2010 11:07 PM, Darren New wrote:
> Initializing an infinite tape for a
> turing machine at least makes it more powerful than one with an
> uninitialized tape.
OK.
> And rule 110 needs an infinitely initialized tape.
I'm still not convinced that this is actually necessary.
In other words, I suspect that rule 110 *is* Turing complete, it's just
that the proof provided is a bit weak.
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
clipka wrote:
> "An initial state (time t=0) is selected by assigning a state for each
> cell."
>
> (Wikipedia)
>
> Isn't that plain enough? You assign a state for /each/ cell. CA's don't
> seem to make any limitations on this.
Well, from that same page:
"""
It is usually assumed that every cell in the universe starts in the same
state, except for a finite number of cells in other states, often called a
configuration. More generally, it is sometimes assumed that the universe
starts out covered with a periodic pattern, and only a finite number of
cells violate that pattern. The latter assumption is common in
one-dimensional cellular automata.
"""
So you "generally" don't start with an infinite aperiodic pattern.
What I was really interested in was a proof that starting with a periodic
pattern (except a finite number of cells) didn't give more computing power
to the CA than starting with a single state (except a finite number of
cells). Because Wolfram is arguing about the computational power of Rule 110.
> Just name /any/ rule for that pattern
I don't think that works, because then it lets the CA calculate stuff a TM
cannot, and I think that would lead to a trivial disproof of the
Church-Turing thesis.
Now, a pattern that differs from a regular repeating pattern in only a
finite number of places? Sure, that's likely good.
But if Wikipedia says a repeating pattern for linear CAs is common, I'll
assume that's sufficient to quell my disquiet with the Rule 110 proof in
that regard. I'd still like to see a proof that having the repeating pattern
doesn't add computational power, which is what the Crawley paper was
apparently discussing. I'll have to take time to look at that closer.
--
Darren New, San Diego CA, USA (PST)
Serving Suggestion:
"Don't serve this any more. It's awful."
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
Invisible wrote:
> In other words, I suspect that rule 110 *is* Turing complete, it's just
> that the proof provided is a bit weak.
I suspect you can build a linear CA that's turing complete. I'm not
convinced that 110 without the infinite initialization can do that.
--
Darren New, San Diego CA, USA (PST)
Serving Suggestion:
"Don't serve this any more. It's awful."
Post a reply to this message
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |
| ![](/i/fill.gif) |
|
![](/i/fill.gif) |
|
![](/i/fill.gif) |
| ![](/i/fill.gif) |