 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
OK, so I'm currently failing to figure this out...
How do you compute the smallest possible (axis-aligned) bounding box for
an ellipse (which is not necessarily axis-aligned)?
Apparently such an ellipse can be represented as
X(t) = Xc + A cos t cos K - B sin t sin K
Y(t) = Yc + A cos t sin K + B sin t cos K
Clearly you need to find the minimum and maximum values for X(t) and
Y(t). But I am apparently too stupid to do this. (And even Wolfram Alpha
can't work it out. Oh, it'll give me the answer if I remove all the
symbolic constants with actual numbers, but that's no help at all...)
It strikes me that the sum of two sine waves of identical frequency is
another sine wave, but I can't seem to apply this fact to obtain a result.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> OK, so I'm currently failing to figure this out...
>
> How do you compute the smallest possible (axis-aligned) bounding box for
> an ellipse (which is not necessarily axis-aligned)?
>
> Apparently such an ellipse can be represented as
>
> X(t) = Xc + A cos t cos K - B sin t sin K
> Y(t) = Yc + A cos t sin K + B sin t cos K
>
> Clearly you need to find the minimum and maximum values for X(t) and
> Y(t). But I am apparently too stupid to do this.
When you're looking for the maximum or minimum of a function the first
thing to look for is in general a zero in the derivative.
For example for X:
dX/dt = - A cos K sin t - B sin K cos t
so dX/dt = 0 => A cos K sin t = - B sin K cos t
or assuming A cos K and cos t are not null (you could make special
cases if needed)
tan t = -B/A tan K
so the bounds for X are
X0 = X( atan(-B/A tan K) )
X1 = X( pi + atan(-B/A tan K) )
Sort and do the same for Y...
--
Vincent
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Vincent Le Chevalier wrote:
> so the bounds for X are
> X0 = X( atan(-B/A tan K) )
> X1 = X( pi + atan(-B/A tan K) )
My God, man, IT WORKS!
> Sort and do the same for Y...
Heh, that should be amusing...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> Vincent Le Chevalier wrote:
>> so the bounds for X are
>> X0 = X( atan(-B/A tan K) )
>> X1 = X( pi + atan(-B/A tan K) )
>
> My God, man, IT WORKS!
That's the good thing about math, you know :-)
More than the result you should keep the method in mind, it's useful in
plenty of problems...
--
Vincent
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> My God, man, IT WORKS!
>
> That's the good thing about math, you know :-)
> More than the result you should keep the method in mind, it's useful in
> plenty of problems...
I was attempting to work out what the result of
A sin t + B cos t
is. I was convinced there was a standard identity for this, but I can't
find it. In the end I came up with
Sqrt(A^2 + B^2) sin (t + atan(B/A))
but I don't even know if that's correct. And I still have to apply it to
my original formula to figure out the result.
Man, who knew a simple ellipse was this complicated?!
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"Invisible" <voi### [at] dev null> wrote in message
news:4b7548f1$1@news.povray.org...
> Man, who knew a simple ellipse was this complicated?!
This is an incredibly important life lesson: the complexity of a phenomenon
is utterly disconnected from the number of syllables needed to describe it.
Sometimes I feel the desire to emphasize this concept to my co-workers with
a heavy, blunt object. Then I take a deep breath, get more coffee, and try
to convince myself that homicide is a detriment to career advancement (well,
in my field, anyway).
--
Jack
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Captain Jack wrote:
> This is an incredibly important life lesson: the complexity of a phenomenon
> is utterly disconnected from the number of syllables needed to describe it.
Exhibit A:
http://www.youtube.com/watch?v=58_s6r7PaKo
It's just a swinging pendulum, after all...
Exhibit B: Rule 30 can be stated in 8 equations. Oh, did I mention? It's
Turing-complete. It can compute any computable function.
Note also that simple /= easy.
x^5 - x + 1 = 0 is "simple". Now try solving it...
Similarly, the Waltz is "simple". Try dancing it sometime; you'll
discover that it's surprisingly difficult, despite being so simple.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> Exhibit B: Rule 30 can be stated in 8 equations. Oh, did I mention? It's
> Turing-complete. It can compute any computable function.
You know, he says that, but I'm pretty sure a CA with an infinite amount of
initialization counts as Turing-equivalent.
--
Darren New, San Diego CA, USA (PST)
Forget "focus follows mouse." When do
I get "focus follows gaze"?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> Exhibit B: Rule 30 can be stated in 8 equations. Oh, did I mention?
>> It's Turing-complete. It can compute any computable function.
>
> You know, he says that, but I'm pretty sure a CA with an infinite amount
> of initialization counts as Turing-equivalent.
The point being that some rules can't emulate a Turing machine, while
others can. E.g., rule 0 maps every possible input to 0, so you can't do
very much with that. Rule 2 maps each 1-bit input to the same output.
And so on. Only a few of the possible rules are Turing-complete.
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
> Only a few of the possible rules are Turing-complete.
I fully understand exactly what he's saying. I'm simply denying that he's
correct, on the grounds that he does an infinite amount of setup before he
even starts running the CA. If he came up with a small rule that would
create the initial pattern in a finite number of steps, then maybe it would
make more sense. But as he described it, he needs to set up an infinite
number of clock pulses before starting the emulation in order to clock the
emulation. I'm not sure that's allowed, any more than it's allowed to set up
an infinite pattern of states on a turing machine before starting.
--
Darren New, San Diego CA, USA (PST)
Forget "focus follows mouse." When do
I get "focus follows gaze"?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"Darren New" <dne### [at] sanrrcom> wrote in message
news:4b758c57$1@news.povray.org...
>
> You know, he says that, but I'm pretty sure a CA with an infinite amount
> of initialization counts as Turing-equivalent.
Wait... California is a Turing machine? Good Lord, that explains everything!
--
Jack
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New wrote:
> as he described it, he needs to set
> up an infinite number of clock pulses before starting the emulation in
> order to clock the emulation. I'm not sure that's allowed
Yeah, that does sound a little suspect...
I think this is just a case of a flawed proof though. I'm pretty sure
the *result* is correct.
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
> I think this is just a case of a flawed proof though. I'm pretty sure
> the *result* is correct.
He's trying to prove that *his* CA is turing complete. I already know there
are lots of turing complete CAs. I'm not sure what "result" you think is
correct?
--
Darren New, San Diego CA, USA (PST)
Forget "focus follows mouse." When do
I get "focus follows gaze"?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Captain Jack wrote:
> "Darren New" <dne### [at] sanrrcom> wrote in message
> news:4b758c57$1@news.povray.org...
>> You know, he says that, but I'm pretty sure a CA with an infinite amount
>> of initialization counts as Turing-equivalent.
>
> Wait... California is a Turing machine? Good Lord, that explains everything!
No. Canada.
--
Darren New, San Diego CA, USA (PST)
Forget "focus follows mouse." When do
I get "focus follows gaze"?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
"Darren New" <dne### [at] sanrrcom> wrote in message
news:4b75c435$1@news.povray.org...
> Captain Jack wrote:
>> Wait... California is a Turing machine? Good Lord, that explains
>> everything!
>
> No. Canada.
Ah, of course... all the pieces are falling into place. The entire country
is itself the tabulating device for Winter Olympics scoring then, I'm
assuming.
--
Jack
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
> I was attempting to work out what the result of
>
> A sin t + B cos t
>
> is. I was convinced there was a standard identity for this, but I can't
> find it. In the end I came up with
>
> Sqrt(A^2 + B^2) sin (t + atan(B/A))
>
> but I don't even know if that's correct. And I still have to apply it to
> my original formula to figure out the result.
I think...
a*sin(t) + b*cos(t) = sqrt(a^2+b^2)*cos(t-atan(a/b))
notice that yours was reciprocal and positive.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> I think this is just a case of a flawed proof though. I'm pretty sure
>> the *result* is correct.
>
> He's trying to prove that *his* CA is turing complete. I already know
> there are lots of turing complete CAs. I'm not sure what "result" you
> think is correct?
That CA #30 (amoung others) is Turing-complete.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
>>> I think this is just a case of a flawed proof though. I'm pretty sure
>>> the *result* is correct.
>>
>> He's trying to prove that *his* CA is turing complete. I already know
>> there are lots of turing complete CAs. I'm not sure what "result" you
>> think is correct?
>
> That CA #30 (amoung others) is Turing-complete.
Why would you think this if the proof is flawed?
--
Darren New, San Diego CA, USA (PST)
Forget "focus follows mouse." When do
I get "focus follows gaze"?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>>>> I think this is just a case of a flawed proof though. I'm pretty
>>>> sure the *result* is correct.
>>>
>>> He's trying to prove that *his* CA is turing complete. I already know
>>> there are lots of turing complete CAs. I'm not sure what "result"
>>> you think is correct?
>>
>> That CA #30 (amoung others) is Turing-complete.
>
> Why would you think this if the proof is flawed?
1. It seems a logical and intuitive result.
2. Nobody has disproved it.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> 1. It seems a logical and intuitive result.
Uh, no?
> 2. Nobody has disproved it.
That's not how math works. "Hey, P=NP! Well, nobody disproved it."
--
Darren New, San Diego CA, USA (PST)
Forget "focus follows mouse." When do
I get "focus follows gaze"?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> 1. It seems a logical and intuitive result.
>
> Uh, no?
Intuitive is in the eye of the beholder, is it not? Besides, you just
said yourself that there are CAs which are known to be Turing-complete;
why not this particular one?
>> 2. Nobody has disproved it.
>
> That's not how math works. "Hey, P=NP! Well, nobody disproved it."
Nobody has proved it either.
A question which hasn't been proven one way or the other is an open problem.
A question which has a proof one way, and would require only a single
counter-example to disprove the other way, I think can be considered proven.
Unless you're talking about the 4-colour problem...
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
> Intuitive is in the eye of the beholder, is it not? Besides, you just
> said yourself that there are CAs which are known to be Turing-complete;
> why not this particular one?
Because the CAs that are turing complete prove they are so by having
building blocks for (for example) XOR and NOT gates, which we already know
are turing complete. In addition, the CAs that are known to be turing
complete don't require an infinite grid to run in but only an unbounded one.
Wolfram's CA requires an initialization of an infinite amount of data before
you start the CA in order for it to emulate a turing machine, as well as
doing an infinite amount of processing each step during the emulation.
Now, granted, a CA theoretically operates on an infinite amount of data each
step. I'd agree the rule is turing complete if (a) someone much smarter than
I agreed that an infinite amount of initialization is acceptable or (b) that
the rule did its own infinite initialization before it started computation.
>>> 2. Nobody has disproved it.
>>
>> That's not how math works. "Hey, P=NP! Well, nobody disproved it."
>
> Nobody has proved it either.
Right. And as far as I'm concerned, nobody proved Rule 30 is turing complete
either.
I mean, it's fine to say "I think it is possible to prove it even tho we
didn't yet", or "I think your objection based on infinite amounts of
initialization is not valid", or "I just have this gut feeling that it's
correct." But "because nobody has disproved it" doesn't add to any of
these. :-)
> A question which has a proof one way, and would require only a single
> counter-example to disprove the other way, I think can be considered
> proven.
Uh, no, there is no proof. There's a flawed proof. But (AFAIK) what he
proved the CA does isn't equivalent to a Turing machine. A proof that's
wrong, or that proves something other than what the author intended, isn't
"proof without a disproof". It's nothing.
Maybe I'm mistaken, and an infinite amount of initialization isn't
problematic to the proof. If so, some sort of citation to why would be handy.
--
Darren New, San Diego CA, USA (PST)
Forget "focus follows mouse." When do
I get "focus follows gaze"?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
I'm a bit puzzled here. The thread starts with ellipses and then, all
of a sudden and out of nowhere, some completely obscure and unexplained
references are made about some mysterious "Rule 30" and something called
a "CA", whatever that means, without nobody explaining what they mean or
what they are referring to.
For all I know CA could refer to Captain America. Maybe he is Turing
Complete. (Don't know what "Rule 30" refers to, though.)
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Warp wrote:
> I'm a bit puzzled here. The thread starts with ellipses and then, all
> of a sudden and out of nowhere, some completely obscure and unexplained
> references are made about some mysterious "Rule 30" and something called
> a "CA", whatever that means, without nobody explaining what they mean or
> what they are referring to.
I'm pretty sure we discussed it before, but unless you're into this sort of
math, I can see where it would be confusing.
CA = cellular automata.
Rule 30 is an encoding of a linear CA's rules as a binary number. You can
take the rules of a linear CA and express them as a truth table, then read
the result of each combination as a binary state, giving you one bit for
each possible input combination the CA will consider. The rule number (30 in
this case) tells you if you interpret the CA's result as a binary number, it
turns out to have the value 30.
For a similar example, "not" is rule 2, "AND" is rule 1, OR is rule 7, and
XOR is rule 6.
XOR:
0 x 0 = 0
0 x 1 = 1
1 x 0 = 1
1 x 1 = 0
rule 6 -^
Wolfram constructed a pattern that uses rule 30 to emulate a turing machine
if you read the results down the page as the linear CA calculates across the
page. That's cool, except he has to put an infinite number of "clock bit"
patterns on the line first. I'm not sure that's legit, since rule 30 doesn't
actually generate its own clock pulses. If he had a rule that created the
clock pulses on an otherwise uniform starting state and which then changed
over to rule 30 afterwards, I'd have no complaints.
But it's like saying "I have this Turing machine that emulates in only 2
states all other turing machines. But only if you start out on a tape where
each prime numbered cell has a non-empty symbol on it first."
--
Darren New, San Diego CA, USA (PST)
Forget "focus follows mouse." When do
I get "focus follows gaze"?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New wrote:
> But it's like saying "I have this Turing machine that emulates in only 2
> states all other turing machines. But only if you start out on a tape
> where each prime numbered cell has a non-empty symbol on it first."
More specifically, it's like calling that two-state machines a "universal"
turing machine. All you need is an infinite amount of computation to prime
it. :-)
--
Darren New, San Diego CA, USA (PST)
Forget "focus follows mouse." When do
I get "focus follows gaze"?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Orchid XP v8 wrote:
>>> 1. It seems a logical and intuitive result.
>>
>> Uh, no?
>
> Intuitive is in the eye of the beholder, is it not? Besides, you just
> said yourself that there are CAs which are known to be Turing-complete;
> why not this particular one?
Are you *sure* that rule 30 is the right CA here? As far as I'm aware
of could find via Google rule 30 is *not* believed to be Turing
complete. It's entirely possible that I missed something, but it's a
class III automaton rather than a class IV CA so there's a reason I'm
doubting this.
It seems more likely that the proof you're talking about was done for
rule 110, which is the CA that Wolfram proposes to be Turing complete,
and there was a later proof by Matthew Cook establishing this provided
proper tape initialization and processing is done.
If you do have a reference giving the proof for rule 30 I'd be
interested to see it since it doesn't strike me as an intuitive result
and thus I'd probably be able to learn something from it.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Kevin Wampler wrote:
> Are you *sure* that rule 30 is the right CA here?
No, actually. I thought that sounded wrong, and 110 sounds much more like
what I remember, but I wasn't about to dig out the 30 pound tome to check. :-)
> and there was a later proof by Matthew Cook establishing this provided
> proper tape initialization and processing is done.
Right. There's a proper proof *providing* the initialization of the first
state is done. That's what I'm not sure is valid. I'm not saying it isn't,
but I'm not convinced it is. AFAIR, the definition of a turing machine
requires anything past a finite initial portion of the tape to be all
initialized to the same symbol.
Sorry for any confusion.
--
Darren New, San Diego CA, USA (PST)
Forget "focus follows mouse." When do
I get "focus follows gaze"?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New wrote:
> Kevin Wampler wrote:
>> Are you *sure* that rule 30 is the right CA here?
>
> No, actually. I thought that sounded wrong, and 110 sounds much more
> like what I remember, but I wasn't about to dig out the 30 pound tome to
> check. :-)
I see. I had asked partially since if rule 30 isn't Turing complete it
provides a nice counterexample to the "it's a CA with non-trivial
behavior so it's probably Turing complete" viewpoint (which you were
also arguing against).
>> and there was a later proof by Matthew Cook establishing this provided
>> proper tape initialization and processing is done.
>
> Right. There's a proper proof *providing* the initialization of the
> first state is done. That's what I'm not sure is valid. I'm not saying
> it isn't, but I'm not convinced it is. AFAIR, the definition of a turing
> machine requires anything past a finite initial portion of the tape to
> be all initialized to the same symbol.
I swear I'd read a nice blog post about this at some point but I cannot
seem to find it again. As far as I remember the main gist was "you have
to be careful with the initialization since it's possible to combine two
non-Turing complete components and get a Turing complete result"
Ahh, I *think* this is what I was remembering:
http://forum.wolframscience.com/showthread.php?s=&threadid=1472
As near as I can tell, maybe it's best to view rule 110 as "weakly
universal" since the universality proof requires an infinite (and AFAIK
non-repetitive) initialization? That seems to convey the idea that it
has some interesting properties with respect to Turing completeness, but
that it's not quite the full-blown form of Turing completeness you'd
normally expect.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New wrote:
> Wolfram constructed a pattern that uses rule 30 to emulate a turing
> machine
I should note that the proof (for rule 110) wasn't actually done by
Wolfram. It was done by Matthew Cook who was interning for Wolfram
Research at the time. Here's a snippet which will hopefully explain why
I think this is worth mentioning:
"The real problem with this result, however, is that it is not
Wolfram's. He didn't invent cyclic tag systems, and he didn't come up
with the incredibly intricate construction needed to implement them in
Rule 110. This was done rather by one Matthew Cook, while working in
Wolfram's employ under a contract with some truly remarkable provisions
about intellectual property. In short, Wolfram got to control not only
when and how the result was made public, but to claim it for himself. In
fact, his position was that the existence of the result was a trade
secret. Cook, after a messy falling-out with Wolfram, made the result,
and the proof, public at a 1998 conference on CAs. (I attended, and was
lucky enough to read the paper where Cook goes through the construction,
supplying the details missing from A New Kind of Science.) Wolfram, for
his part, responded by suing or threatening to sue Cook (now a penniless
graduate student in neuroscience), the conference organizers, the
publishers of the proceedings, etc."
From here: http://www.cscs.umich.edu/~crshalizi/reviews/wolfram/
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Kevin Wampler wrote:
> I see. I had asked partially since if rule 30 isn't Turing complete it
> provides a nice counterexample to the "it's a CA with non-trivial
> behavior so it's probably Turing complete" viewpoint (which you were
> also arguing against).
Fair enough.
> I swear I'd read a nice blog post about this at some point but I cannot
> seem to find it again. As far as I remember the main gist was "you have
> to be careful with the initialization since it's possible to combine two
> non-Turing complete components and get a Turing complete result"
Yes, that was my concern. In particular, a TM with an infinite pattern on
the initial tape isn't obviously as simple as a similar TM with a finite
pattern on the initial tape. It's not clear to me whether the same is true
of a CA that does an infinite computation at every step to start with.
How much of the human's understanding of what the pattern means is really
involved? How much of the infinite pattern being unimportant is just the
human's understanding that "oh, that's just the clock pulse". How much of
that infinite complexity is dismissed only because of "understanding" which
is specifically denied to the formalism?
For example, a TM with any finite initial pattern on the tape can be
trivially turned into a finite TM with a completely blank tape to start,
simply by prepending a series of instructions to write the appropriate
pattern to the tape. This isn't true of an infinite pattern, even if it's
repetitive. It *is* true of a CA, but you'd have to change the rule of the
CA in the middle of evaluation, and there's no obvious way in the formalism
to do that, since CAs don't keep any sort of state (corresponding to the
head position and state number) outside the actual "tape." I just never got
into the whole deal enough to know the answers to such questions, and I'm
not sure it even makes a difference. It would be interesting to know whether
there's a proof or a disproof of whether an infinite repetitive initial tape
for a TM makes a difference in what you can compute.
> Ahh, I *think* this is what I was remembering:
> http://forum.wolframscience.com/showthread.php?s=&threadid=1472
That seems to be talking about TMs, not CAs. Two different beasts when
talking about infinite tapes, since a CA does infinite computation at every
step, while a TM does not. I'm also almost certain that the Rule 110
universal machine starts with a repeating pattern (other than the "program")
so would fall under the "computational properties of linear cellular
automata on configurations that differ from spatially periodic ones in only
finitely many places" rule. Since the author seems to claim (in the
abstract) that "is the same on these configurations as on the space of
finite configurations" then it would seem they think they proved that Rule
110 is indeed turing complete in spite of needing infinite initialization.
The 2,3 TM is interesting only in that it's tiny. But if you're going to
argue that simple systems can make really complex results, the fact that a
2,3 TM can do so doesn't seem that much more surprising than a 3,5 TM for
example. Especially since all the TMs require sophisticated interpretation
of their results to support any of these proofs - you already have all kinds
of encoding issues outside the TM to interpret what's on the tape to figure
out the isomorphisms with other machines.
I think Wolfram's wanking with his smallest-TM contests in a way that
doesn't really add anything to his basic premise.
Interesting links tho. I'll have to read them in my copious spare time. ;-)
> As near as I can tell, maybe it's best to view rule 110 as "weakly
> universal" since the universality proof requires an infinite (and AFAIK
> non-repetitive) initialization? That seems to convey the idea that it
> has some interesting properties with respect to Turing completeness, but
> that it's not quite the full-blown form of Turing completeness you'd
> normally expect.
Sure. I just didn't find it interesting, given there *are* CAs that are
known to be (and easily provable to be) turing complete. OK, so now there's
a linear one. So? Only Wolfram crowing about how trivial it is made it
interesting, and I didn't consider it to be particularly trivial if it
needed an infinite amount of initialization. The Conway CAs that are indeed
turing complete have initial states that are scaled relative to the size of
the turing machine they're emulating, so the fact that they're "big" in some
absolute measure isn't all that interesting. They're still only 4 rules, at
absolute worst a 512-range CA instead of a 256-range (or was Wolfram's a
128-range?).
--
Darren New, San Diego CA, USA (PST)
Forget "focus follows mouse." When do
I get "focus follows gaze"?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Kevin Wampler wrote:
> "The real problem with this result,
Huh. As I said, it seemed more like Wolfram wanking than any sort of
important result. He's clearly trying hard to make a name for himself in
history. Kind of sad to watch, really.
--
Darren New, San Diego CA, USA (PST)
Forget "focus follows mouse." When do
I get "focus follows gaze"?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New wrote:
>
> That seems to be talking about TMs, not CAs.
I can't believe I missed that. Once I read enough to see that the was
the link I remembered I clearly didn't read enough extra to verify that
it was actually talking about a CA! That'll learn me. The overall gist
still seems relevant though.
>
> Sure. I just didn't find it interesting, given there *are* CAs that are
> known to be (and easily provable to be) turing complete.
Personally I find it interesting, but interesting in a "ok, that's sort
of neat" way rather than as providing any sort of fundamental insight.
I basically agree with your assessment otherwise though.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Kevin Wampler wrote:
>> Sure. I just didn't find it interesting, given there *are* CAs that
>> are known to be (and easily provable to be) turing complete.
>
> Personally I find it interesting, but interesting in a "ok, that's sort
> of neat" way rather than as providing any sort of fundamental insight. I
> basically agree with your assessment otherwise though.
Well, yeah. I mean, it was interesting that something as simple as a tiny
linear CA could be made turing complete without actually obviously emulating
a machine. I didn't find it "fundamentally" interesting. Certainly not
something I'd call a "new science" for example. I.e., I think I'm agreeing
with you.
--
Darren New, San Diego CA, USA (PST)
Forget "focus follows mouse." When do
I get "focus follows gaze"?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Kevin Wampler wrote:
> Are you *sure* that rule 30 is the right CA here?
>
> It seems more likely that the proof you're talking about was done for
> rule 110, which is the CA that Wolfram proposes to be Turing complete,
> and there was a later proof by Matthew Cook establishing this provided
> proper tape initialization and processing is done.
Hmm, maybe you're right. I don't memorise these code numbers...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
WIN!
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>>> Sure. I just didn't find it interesting, given there *are* CAs that
>>> are known to be (and easily provable to be) turing complete.
>>
>> Personally I find it interesting, but interesting in a "ok, that's
>> sort of neat" way rather than as providing any sort of fundamental
>> insight. I basically agree with your assessment otherwise though.
>
> Well, yeah. I mean, it was interesting that something as simple as a
> tiny linear CA could be made turing complete without actually obviously
> emulating a machine. I didn't find it "fundamentally" interesting.
> Certainly not something I'd call a "new science" for example.
If you could prove not that one particular "simple" system is
Turing-complete, but that huge classes of simple systems are, *that*
would be an interesting result.
(Presumably such a result would include deciding exactly when a simple
system is or isn't Turing-complete.)
I still wouldn't describe it as a "new kind of science". Indeed, from
what I can gather, NKS isn't some sweeping new paradigm. It's just a new
and unusual way of looking at and thinking about things. That's not to
say there aren't interesting things to be learned from this point of
view, but it hardly rocked my world.
Fractal geometry already tells us that simple rules can generate complex
behaviour. Chaos theory already tells us that deterministic, simple
systems can still be highly unpredictable. NKS doesn't seem to add very
much. There's a few small, specific things which are interesting, but
it's not nearly as radical as people are saying.
But then again, isn't this the same Mr Wolfram who claims that
Mathematica fundamentally transforms the way computer mathematics
happens? Or that Wolfram Alpha is going to revolutionise the human race?
Sure, Mathematica is a great piece of software, but I guess we should
take anything Mr Wolfram says with a pinch of salt...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Darren New wrote:
> Right. There's a proper proof *providing* the initialization of the
> first state is done. That's what I'm not sure is valid.
And I still think it ought to be possible to do this without all that
initialisation. I just haven't proved it yet. ;-)
(Don't hold your breath for that...)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> If you could prove not that one particular "simple" system is
> Turing-complete, but that huge classes of simple systems are, *that*
> would be an interesting result.
Um, we already have that. It's called "A Turing Machine." :-) I mean, that
was the whole point of defining Turing machines, then coding a universal
turing machine, then proving that all kinds of multi-tape multi-this
multi-that all reduce down to the same single-tape single-program
UTM-capable machine.
> (Presumably such a result would include deciding exactly when a simple
> system is or isn't Turing-complete.)
We already have that too.
> I still wouldn't describe it as a "new kind of science". Indeed, from
> what I can gather, NKS isn't some sweeping new paradigm. It's just a new
> and unusual way of looking at and thinking about things. That's not to
> say there aren't interesting things to be learned from this point of
> view, but it hardly rocked my world.
No. I think he was asserting that science should look at computational
systems as the basis of science, rather than (say) the closed form fomulas
of how the world works that science uses now. However, since he didn't do
what you're talking about, namely being able to point at the attributes of a
system and determine how computationally complex it is, he failed at that task.
> Fractal geometry already tells us that simple rules can generate complex
> behaviour. Chaos theory already tells us that deterministic, simple
> systems can still be highly unpredictable. NKS doesn't seem to add very
> much. There's a few small, specific things which are interesting, but
> it's not nearly as radical as people are saying.
I don't think anyone but Wolfram are saying it's radical. :-)
> But then again, isn't this the same Mr Wolfram who claims that
> Mathematica fundamentally transforms the way computer mathematics
> happens? Or that Wolfram Alpha is going to revolutionise the human race?
>
> Sure, Mathematica is a great piece of software, but I guess we should
> take anything Mr Wolfram says with a pinch of salt...
Yep.
--
Darren New, San Diego CA, USA (PST)
Forget "focus follows mouse." When do
I get "focus follows gaze"?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> If you could prove not that one particular "simple" system is
>> Turing-complete, but that huge classes of simple systems are, *that*
>> would be an interesting result.
>
> Um, we already have that. It's called "A Turing Machine." :-) I mean,
> that was the whole point of defining Turing machines, then coding a
> universal turing machine, then proving that all kinds of multi-tape
> multi-this multi-that all reduce down to the same single-tape
> single-program UTM-capable machine.
Sure. But a UTM is carefully *designed* to be universal. Wolfram asserts
that many kinds of things "just happen to be" universal. Now if he had
offered a proof rather than an assertion (i.e., a theorum stating
exactly which kinds of things are Turing-complete), that might have been
interesting. As it is, he just goes through a collection of CAs and
demonstrates that just one of them is definitely Turing-complete.
>> (Presumably such a result would include deciding exactly when a simple
>> system is or isn't Turing-complete.)
>
> We already have that too.
Really? So you can tell me exactly which CAs are or aren't
Turing-complete then?
(Actually, I have a sinking feeling the general question might be
undecidable, but anyway...)
> I think he was asserting that science should look at computational
> systems as the basis of science, rather than (say) the closed form
> fomulas of how the world works that science uses now. However, since he
> didn't do what you're talking about, namely being able to point at the
> attributes of a system and determine how computationally complex it is,
> he failed at that task.
Yeah, even after reading NKS, I'm still not *exactly* sure what he was
getting at. Maybe he isn't either...
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Invisible wrote:
> Sure. But a UTM is carefully *designed* to be universal. Wolfram asserts
> that many kinds of things "just happen to be" universal.
No, he asserts that many things just happen to be capable of being designed
to be universal. A UTM is just the kind of TM that's universal. Rule 110 is
only universal if you initialize it with the appropriate program in the
cells to start with.
> demonstrates that just one of them is definitely Turing-complete.
It's turing complete only when running on the right program, initialized
with the right set of data on the cells. 110 itself doesn't calculate
anything except what rule 110 says to calculate.
>>> (Presumably such a result would include deciding exactly when a
>>> simple system is or isn't Turing-complete.)
>>
>> We already have that too.
>
> Really? So you can tell me exactly which CAs are or aren't
> Turing-complete then?
Sure. The ones that can emulate arbitrary turing machines are turing
complete. :-) Oh, you mean, can I tell that just by looking without doing
any mathematical proofs? No. :-)
> Yeah, even after reading NKS, I'm still not *exactly* sure what he was
> getting at. Maybe he isn't either...
He's getting at "Hey! Hey, look at me! I should be famous!"
--
Darren New, San Diego CA, USA (PST)
Forget "focus follows mouse." When do
I get "focus follows gaze"?
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> Sure. But a UTM is carefully *designed* to be universal. Wolfram
>> asserts that many kinds of things "just happen to be" universal.
>
> No, he asserts that many things just happen to be capable of being
> designed to be universal. A UTM is just the kind of TM that's universal.
> Rule 110 is only universal if you initialize it with the appropriate
> program in the cells to start with.
Like I said, I think you can set up the CA more easily than the proof
demonstrates. But whatever...
--
http://blog.orphi.me.uk/
http://www.zazzle.com/MathematicalOrchid*
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
