Developing a New Kind of
Science Website as a
Software Project Course
Rudy Rucker, Department of Computer Science, San Jose State University
Last Update: May 16, 2003
Jumps to Main Sections:
Course Syllabus for CS 240: Software Project,
Spring, 2003.
Four Sketchily Proposed Research Paper Topics
To teach a projects class in which students create some software, write a research paper, and learn about Stephen Wolfram’s A New Kind of Science (called NKS for short).
To create a website to present some of the ideas in NKS. We will include text, links, and interactive programs written in Java. Some of the programs will directly emulate programs discussed in NKS, others will be original to our site.
We will call the site NKS-SJSU, although “Automatism” was a contender.
The NKS-SJSU web site will be hosted by Monkeybrains of San Francisco, with the website located at http://sjsu.rudyrucker.com.
· Use a uniform template across the pages of the site.
· Provide a complete and well-commented set of links on topics relating to NKS.
· All code will be shareware and open source.
· Programs will be interactive Java applets that run in a continuous “lava-lamp” mode.
· Programs will have a good, consistent interface that accepts either keystrokes or mouse clicks.
Develop a simple Template page to use for every one of our pages.
The top page index.htm should provide some kind of compact map of the whole site, should load rapidly (no applets and few bitmaps), and should have a one paragraph description of what the site is.
The second level Applet and Paper pages will be two-column tables, with each column holding an N-row table. The cells in the one column can be links or illustrations. The cells in the other should hold blocks of text, illustrations or applets. Generally pages should not scroll down more than two or three screens.
The third level student pages will contain the applets and the papers that the students write. Use the template for these pages as well.
We’ll have a few base pages maintained by Rucker and the class, with links to pages in individual directories maintained by the students. We will host the site on www.monkeybrains.net.
Our second level links page will be a table that has an interactive quality that lets us sort according to a selected column, like an Excel spreadsheet. Column titles might be as listed below. For some columns like “Has Java Apps,” the entries could just be Y or N or, perhaps better, could be a number from 0 (for none) to 1 (for a few, but not very good) to 5 (for lots of them or very good). We can poll the class for the ratings.
Column titles might be these. Site Name (with link in the name) followed by brief description, Author(Last name first), Has Java Apps, Has Downloadable Applications, Is Mostly Text, 1D CAs, 2D CAs, 3D CAs, Turmites, Turing Machines, Other Automata. Possibly we’ll include a thumbnail image of each site, but that’s not important at first, so put this column last.
Getting the interactivity of the table was tricky, but Harry Fu found some JavaScript to do it.
We’d like to do exhaustive searches of various kinds of computation spaces, so we should develop at the very least a software pattern for this activity and possibly a software framework with some reusable classes. Also want to allow user interaction.
A framework or class for the various kinds of rules would also be useful. The framework might be set up so we can do automated searches of these rule spaces to find certain kinds of rules.
In practice we didn’t in fact manage to develop a common shared framework for the classes used in the various applets, although we did try and develop a common UML diagram --- though it’s not certain how well the students stuck to it. The professor didn’t look at the student’s source code, and confined his comments to requests regarding the applets’ user interfaces and features sets.
Professor did try and enforce that every applet uses double-buffering to prevent tearing and flickering of the screen image.
In this course we are going to create a website related to the material in Stephen Wolfram’s book A New Kind of Science.
You will be creating HTML pages and Java applets for the site we will build. In addition, you will write a term paper which may be posted on the site. Note that the site is going to be frequently updated during the semester.
The material will deal largely with cellular automata (CAs).
Our website project
will primarily use HTML and Java. We will also allow the option of modifying
the CAPOW C++ Windows software to create new downloadable files for the site.
If this is a small class (less than 15 students), students will do individual applet projects. If the class is larger we may do the apple projects in small teams of about three each.
The writing projects will in any case be individual. The writing project should be related to topics in Wolfram's book. Although it is recommended that your writing project be related to your applet project, this is not strictly necessary. The professor will post a list of suggested writing project topics.
The applet projects and writing projects will be discussed and designed by the students and the professor over several iterations. Each applet project must be based on a solid object-oriented design. We may do some programming work in class
The required text
for the course is::
·
Stephen Wolfram, A New Kind of Science (Wolfram Research
International, 2002).
The applet and writing projects will involve several preliminary assignments. The applet projects will include specifications, prototype, alpha and beta releases, and class-room demos. The writing projects will include proposal, short draft, longer draft, final draft.
Grading of the applet projects will be based on (a) Lack of Bugs, (b) Originality and Difficulty of the Project, (c) Simplicity and Strength of User Interface, (d) Quality of Printed and Online Documentation, (e) Classroom Presentations and Demos.
The writing project will be graded on (a) Relevance of the topic to NKS, and the complexity of the topic, (b) Depth of specific material gone into and originality of ideas, (d) Breadth of research and presentation of known results, (c) Writing quality: style, grammar, spelling (e) Illustrations. Be careful not to plagiarize any of your paper, as the professor will use web search tools to check for this.
The prerequisite for
this course is (a) grad student status or, (b) CS 160 Software Engineering with
B- grade or higher.
(1 ) 6 Pts. SITE. Make a web site and email me a link to it. Subject should be CS240. Capital "CS" and no spaces. If you have an email account, you may already have access to host a web site with your service provider. Look in to it. If you don't have access to web site hosting, you might consider getting a free account (at least they SAY it's free...) at Yahoo's Geocities or elsewhere. If all else fails, hand in your website on a disk (floppy disk, ZIP disk, or CD), although I will deduct a point for doing this. Do not, repeat DO NOT email me a large *.zip file with your website. What goes on the web page? See parts (2), (3), (4) and (5). For maximum credit, put something more on the page. Maybe an applet that you wrote. Maybe the beginnings of an interactive essay.
(2) 5 Pts. DESIGN
IDEAS. Write up some ideas about how we might design a class-wide website relating
to Wolfram's book. Make suggestions about (a) how to organize the directories
so that individuals can make contributions but so there is a single interface
for people to browse our creation from, (b) what kind of text to put on the
pages, and what kind of text, in particular you might want to work on, (c) what
kind of Java applets we can put on our pages.
This written material should appear on your web page.
In addition this written material should be printed out and handed in.
(3) 3 Pts. APPLET. Get the source code for Mirek's MJCell, change the source so that "built by YOUR NAME" appears in the caption bar, compile and build the applet, and place a button to start it on your web page. If you like, you might want to change the parameters that MJCell starts up with. In addition, you might want to put several buttons to launch MJCell with different parameters.
(4) 1 Pts. LINKS. Put a few links on your page, preferably some new links that you've found.
(1) 3 Pts. Move your website files to your new directory on sjsu.rudyrucker.com. Note that I'm moved my Projects page to this site as well.
(2) 3 Pts. Try and create an interactive spreadsheet for the CA links. There is some discussion of this on the projects page. One approach is to create it in Microsoft Excel and save or "publish" it into html format. I've been having trouble getting this to work. An alternate approach might be to use some special feature of Java or HTML which you might know about. The goal is to have a spreadsheet where you can sort the rows in different ways by clicking on the headers of the columns.
(3) Hand in these written materials:
(a) 3 Pts. Description of which Java applet you are going to try and program.
(b) 3 Pts. A UML diagram of the classes you think you'll use
(c) 3 Pts. Description of the research paper you intend to write. Life may be easier if your paper and your applet are closely related, but this isn't absolutely necessary.
This is a redo of Assignment 2. If you simply give me the same Assignment 2 again, you'll get a zero. Rethink and redo.
(1) 4 Pts. Specification of the Java applet you want to write. This must be one of the applets I suggest on the class plan page at Proposed Applet Projects.
(2) 4 Pts. UML diagram for your applet in the format we discuss in class.
(3) 4 Pts. Research topic you want to write on. Should be a topic I suggested on the class page.. Look up and list at least three references: pages in Wolfram's book, refs from his notes, pages you find in Google, or ask me in person. Write at least half a page, with a full page being preferred.
(1) 3 Pts. Redraw your UML diagram one more time. Make it cleaner. Do several drafts in pencil to organize it nicely. Choose reasonable names for your classes to match what you will code. List the key methods and their arguments. Don't have any lines crossing each other. Use only the hollow-headed inheritance arrow, the diamond-tailed composition line, and the barbed navigation arrow.
(2) 8 Pts. Post an alpha version of your applet on your page. Grade depends both on whether it works and on the difficulty and number of features.
(3) 4 Pts. Outline your paper, possibly changing it as I requested. Make the outline more than one page long, single spaced, or more than three pages long double spaced. Break the outline into 3 or 4 sections with section titles, possibly using subsections as well. List at least three paper references and two or three website references.
1)
What is the new scientific paradigm that Wolfram proposes?
2) Explain in words and pictures what CA Rule 30 is.
3) What are the four classes of computations that Wolfram discusses?
4) Describe two simple kinds of computation other than 1D CAs, explaining for
each of them what kinds of behaviors the four different classes would show.
5) Give a simple example of complexity emerging from a simple iterated
arithmetic computation. What are some
of the issues in simulating such a computation.
6) Give an example of a 1D continuous-valued CA.
7) What is the relationship between continuous-valued CAs and differential
equations?
8) What are the three types of randomness in nature that Wolfram talks
about? Explain in terms of a 1D CA.
9) Describe the following 2D CAs: Vichniac’s Vote rule, the Game of Life,
Brian’s Brain.
10) Describe a 2D CA rule for generating patterns like crystals.
11) Describe a 2D CA rule for simulating fluid flow.
12) Why does Wolfram say his experiments with simulated fluid flow undermine
the belief that randomness is always a result of sensitive dependence on
initial conditions.
13) What does Wolfram have to say about the process of natural selection that
produces the spots on a butterfly’s wings?
14) What simple class of rules might be used to account for the shapes of the
leaves and the branching of plants?
15) How does Wolfram propose accounting for the 137.5 degree angle in
phyllotaxis?
16) What is a CA rule that can create spots and stripes like on animal coats?
17) What is Wolfram’s model for the financial market?
18) How many 1D radius-1 4-state CAs are there?
19) How many 1D 3-state 2-symbol Turing machines are there?
20) Draw and explain the UML for the applet you are building for this
course. Make the diagram as simple as
possible, that is, don’t list more than two methods per class.
Sixty-Four Points. Eight eight-point problems. Neatness counts, particularly in diagrams. If you mess up a diagram cross it out and start over.
(1) (a) (4 pts) Draw the lookup table used to compute Rule 110. (b) ( 4 pts) Draw the first five rows of Rule 110, starting from a single marked cell.
(2) Give examples of 2D CA behaviors which correspond to Wolfram’s four classes. Number your answers (a) ( 2 pts) through (d) ( 2 pts). For each answer describe a kind of 2D CA rule behavior and, if you can, give the name of a particular rule of that kind.
(3) (a ) (4 pts) How many 1D radius-1 3-state CAs are there? (b) ( 4 pts) How many 1D 3-state 2-symbol Turing machines are there?
(4) (a) ( 4 pts) Describe the 1D radius-1 continuous-valued CA which simulates the Heat Equation, also known as the Diffusion Rule, (with no extra heat added in). (b) ( 4 pts) Describe the 1D radius-1 continuous-valued CA which simulates the Wave Equation. [Hint: the two answers are very simple.]
(5) (a) ( 2 pts), (b) ( 2 pts), (c) ( 4 pts) What are the three types of randomness in nature that Wolfram talks about? For full credit draw three diagrams (similar to 1D CAs), one for each kind of randomness, and give a specific example of Wolfram’s preferred type of randomness (c).
(6) (a) ( 4 pts) and (b) ( 4 pts). Give two distinct examples of biological pattern or form which are probably the result of simple computational rules.
(7) (a) ( 4 pts) Describe Wolfram’s model for the financial market. (b ) (4 pts) Tell me the code-numbers of the equivalent “Bull” and “Bear” 1D radius-1 2-state CA rules.
(8) (a ) (2 pts) List the main classes of your own that you are using in your applet, stating their names and their purposes. Use plain English, not Java code. (b) ( 6 pts) Draw the UML for the applet you are building for this course. Make the diagram as simple as possible, that is, don’t list and class members or methods, just show the class names mentioned in part (a), connected by inheritance lines, by navigation lines, and by composition lines. Be very careful to use the right kinds of line symbols.
(a. 10 points.) Second alpha (or, stretching a point, the “beta”) release of your applet. Should function. Should have buildable source code up for download as well. Put on the class web page in your \applet subdirectory. Put a picture and description of your applet on the class Applets page.
(b. 10 points.) Write a first draft of your report, check it for content, use spell check to correct your spelling. Possibly use grammar check to correct your grammar. If you are not a native English speaker, have an English-speaking friend check your English.
Improve the style and content and write a second draft.
Submit a print-out of the second draft, also save as HTML and post in the \paper subdirectory of your site. Put a description of your paper on the class Papers page.
(c. 5 points.) Give a presentation in class describing your applet and your paper.
( The 75 points are: 25 for the Presentation, 50 points for the paper. If there are major problems with the paper, you can resubmit it up until the final class meeting. Recall that the writing project is supposed to count for 30% of the course, which is why this assignment is weighted so heavily. The total points over all assignments is 246, and thirty percent of 246 points is 74, close enough to 75.)
We’ll like to have 3 twenty-minute presentations per class for four classes to cover our 12 class members.
This is the final version of your written report. Give the final printed version to the professor and give a twenty-minute oral presentation on your report with Powerpoint slides. Post an HTML version in your \paper subdirectory. Put a link to your paper on our main jdkpapers.html page.
To prevent plagiarism, professor will search Google for unusual phrases in your paper. As long as any evidence of plagiarism is found, you will get a 0 on the paper. Whatever you haven't written in your own words, you must place in quotation marks and attribute!
I’ll return the papers and go over the final versions of your applet, which should be posted on the site by now, and should include the various interface and features changes we’ve discussed in class.
Rucker recently completed a review of Wolfram’s A New Kind of Science which appeared in the American Mathematical Monthly, November, 2003. Here’s a PDF version of Rucker's AMM Review of NKS. Rucker also gave several talks on Wolfram’s book in Belgium in Fall, 2003. Rucker's Powerpoint Talk on Wolfram's Book.
Brian Silverman and Mitch Resnick of MIT have an “Emergence” site which is an essay with active Java illustrations. This represents a really nice fusion between a programming project and a writing project, and serves as a kind of role model of one thing we want to do. In practice, you might work on the underlying program for a page-sequence like this with someone else, and then each write your own “interactive essay” using the software.
The Wisconsin mathematician David Griffeath runs a very comprehensive CA site called The Primordial Soup Kitchen.
A useful, wide-ranging resource on CAs is this site http://cafaq.com
The source for the Java applet used on the Emergence site is downloadable here. Regarding this source, Brian Silverman says, "There's only one .java file. The rules and starting position are defined in text files read by the applet. Unfortunately the applet is very old -- back from the Java 1.0 days. This doesn't prevent the class files from working but does make it hard to rebuild with a more recent Java. Feel free to update it. The big change would be moving to the current event model."
Griffeath’s Primordial Soup Kitchen site includes a list of links to Java-enabled CA web pages.
(Suggested by Gauri) Another CA written in Java is by Christopher David Osborn available at http://www.softrise.co.uk/srl/caworld.shtml
Here is a really nice interactive Wator simulation applet with two kinds of species, fish and sharks. Although this could be implemented as a CA, it's probably done as an alife simulation with a bunch of agents that are fish or sharks. Note that the Cellab application has a Wator mode with three species, done as a CA.
Rudy Rucker and John Walker wrote a CA package called Cellab that is a DOS executable you can download. The page also includes a long, thorough survey of CAs written by Rucker. Note that if reading the manual online is hard due to your connection, you can download the manual and read it offline.
Rudy Rucker and a team of SJSU students created a package called CAPOW. CAPOW is a Windows executable which focuses on continuous-valued CAs.
The most amazing Java CA web site of all is MJCell, maintained by the Polish programmer Mirek Wójtowicz. This is the most complete Java CA applet I’ve ever seen. What’s more, Mirek has his MJCell source code up for free download! An early assignment for this course will be to get Mirek’s code, build it on your machine, and work out a UML diagram of his code. Note on MJCell (from Gauri). Mirek's code was built with JDK 1.1.8. If you compile it with JDK 1.3 or JDK 1.4 you will find a couple of "errors" you need to fix; these are features of the Java language that have changed between releases (this is one thing I dislike about Java, that they don't maintain backwards compatibility among the releases). The errors and fixes are as follows.
Error 1) ambiguous call to List in MJPatternsList.java and MJFavourites.java.
Fix 1) Use java.awt.List instead of only List.
Error 2) Constant expression needed in func KeyDown in file MJCellUI.java.
Fix 2) Use Event.F1 instead of evt.F1 (evt is an object of Event class ) in the
switch case statement.
Stephen Wolfram has a series of Mathematica notebooks illustrating his book available for download. The catch is that, in order to view and use the interactive notebooks you have to have Mathematica 4.0. Older versions of Mathematica such as 3.0 don’t seem to work properly with these notebooks. The web site gives you the impression that you can use the notebooks with the free (8.7 Meg) MathReader 4.0 software for reading Mathematica notebooks, but the notebooks only have the source code used to generate Wolfram’s graphics, and MathReader is crippled so as to be able to do the computations necessary to generate the graphics, so in other words, all you see is the same formulae you can find in the footnotes of Wolfram’s book, so downloading the reader for these particular notebooks is in effect a waste of time. Apparently Wolfram’s formulae do come to life if you have a full working copy of Mathematica 4.0, but I haven’t had a chance to test this.
Another way to see Wolfram’s illustrations live is to buy his A New Kind of Science Explorer, which includes the same free notebook material plus the Mathematica engine to run them, plus a bit more of an interface. I find the Explorer ware not very nice use, though. The interface is slow, and heavily dependent on mouse clicks, which gets tiresome. Also the images are not displayed in a live, ongoing fashion, as is more common for cellular automata software. I prefer CAs that can be run in what I call “lava-lamp” mode, meaning that you turn them on and watch them for as long as you like. Wolfram’s illustrations for his book are invisibly computed in the background and then displayed all at once.
Note that there is a product called Web Mathematica which runs a Mathematica engine on the server. Clients send in Mathematica code and get images back. In principle we could use this instead of writing Java applets for our site, but don’t think this would be a practical option because (a) we’d have to pay Wolfram Inc. a fee to use Web Mathematica, (b) we’d have an application server on our site (c) this doesn’t sound like a scalable architecture --- what if lots of users are requesting images at the same time? (d) it doesn’t let us post standalone open source code.
Show the classic radius-1 two-state CAs.
The two-state totalistic radius 2 Rule (c) on p. 692 looks very pretty.
The rule on p. 740 looks good for lava-lamp mode.
Have an interactive CAPOW-like applet showing nine radius-1 16-state CAs that user can evolve.
The Financial Market Model.
Reversible 1D CAs, in particular the one used to illustrate local avoidance of the Second Law of Thermodynamics.
The squaring rule on p. 639.
A prime-listing rule on p. 640.
Repeated multiplication by 3 in base 2 performed by a CA with 11 colors, p. 661
1D Turing machine pictures. Maybe two applets, one basic, and one with the CAPOW interface.
On p. 707, Wolfram describes what is the simplest known universal Turing machine; it emulates Rule 110. Implement this in a lava-lamp mode. Also consider the machines on p. 708. You may want to use Wolfram’s trick on only displaying a new line when the Turing machine head reaches a new maximum distance from its starting position.
"Busy Beaver" Turing machines are interesting, these are guys that do halt eventually, but run as long as possible before halting.
Turmites, vants.
Is there a nice glider that doesn’t go in a straight line? The answer is yes, see a very cool site by Ed Pegg on Turmites.
I did some work on this, see my Boppers program. It would be good to apply Wolfram’s principles to examining the 2D Turing machine “turmites” in Boppers . Use the simplest possible turmite, like start with 4-direction 2-state, and exhaustively search the possibilities. Fooling around with the ware just now I can find repeating and random, but not nested or localized structures.
In the past, I tended to crank up the directions and states until I got some nice behavior. Wolfram would argue that I’m coming close to putting in the behavior that I want to observe, and it would be more useful to find the interesting stuff in the simpler rules.
So we could do an exhaustive search of Vant/Turmite space.
Note also that if you have pairs of vants, you can get interesting stuff more easily.
I can’t remember the precise difference, between “vant” (Christopher Langton’s word) and turmite (the word I got from Dewdney, who in turn got it from a grad student at Stanford whose name I temporarily forget). I think it might have to do with whether the move part of the Out is a “turn in degrees” or a “turn to some preset direction.”
Continuous-valued 1D CAs, let’s to the untested asymmetric forms.
The rules on p. 156-157. y = neighborhoodaverage + a MOD 1.0 does some complex stuff for certain a values between 0 and 1. Or try y = avg * b MOD 1.0. p. 160.
Possibly try to do the equations on p. 165 and 166 using the Capow methods.
“I suspect that essentially all the phenomena that we have observed in discrete systems...can in fact also be found even in continuous systems with fairly simple rules.” p. 168. This is a very good research opportunity! Find a simple continuous valued CA that is numerically stable under not that tiny of a cell size so that your CA represents a numerically realistic solution, and have gliders in it.
Note that the heat equation type things are already probably universal, but the wrapping part isn’t physical. But the CAPOW Wave or Wave Oscillator look like they could do something.
Page 243, 244. Looks at newC = (C + L + R)/3 + a, draws it nicer by drawing the difference between each cell and its neighbor, thus removing the ugly stripes (check footnote for details.). Then he looks at newC = (C + b*(L + R))/3 + a, which seems to give even nicer rules. Why not go ahead and throw out symmetry newC = (C + b*L + c*R))/3 + a.
Discrete valued 2D CAs. Maybe use Mirek and Modern CA for these.
Continuous valued 2D CA Reaction Diffusion to get spots as in Capow.
Multiplication by 3.
The Snowflake model. p. 370-371. Rule: cell becomes black if it has exactly one black neighbor. Looks better on a hexagonal grid.
Mobile automata like on p. 75. Generalized mobile automata.
A two-state replacement system, p. 91.
Possibly simple assembly language programs, find a way of having a “gene” for a short program that gets interpreted realtime, p. 101. Cf. my assembly language Rule 30.
The thing on p. 125-127 about getting series Bn of bit strings by picking B0 as you like, and letting Bn+1 be Bn + Bn’, where Bn’ is the string Bn written in reverse order.
Try a pendulum and magnets with integer values. I originally wrote my Chaos the Software pendulum and magnets to run in integer arithmetic. I did this out of necessity, to keep the speed up, but, as Wolfram would say, “little did I realize I was making a fundamental breakthrough.”
Point is, an integer-valued pendulum and magnets is no doubt a universal computer.
But, would continuity ruin the computation, with all those bits getting excavated?
I think chaos theorist refer to a continual rounding off as “dissipative.” I seem to recall from Lorenz’s little book that the more interesting kinds of chaos are found in dissipative dynamical systems.
Show slices of a 3D stack of 2D CAs, possibly using “fog” to show all lit cells on a level. p. 248
Show a 3D stack of 2D CAs
Or to show a 3D CA.
These are some very sketchy suggestions, mentioning things I question, disagree with, or want to study further. This list is very preliminary. In reading this, keep in mind, that I do think W's book is of great impotance. But there are some areas that invite discussion.
Brian Silverman makes the point that computational irreducibility doesn't necessarily mean there was no hope for predictions. You can, after all, do much better than a very inefficient universal computation. But --- and I guess this is Wolfram’s point --- you still can only predict the thing by simulating it, and not by writing down a magic formula like the y = -x^2 that predicts the ballistic curve.
But one should work this out correctly. What Wolfram really meant to say is that a computation is irreducible if you can’t get a logarithmic speed-up. That is, the computation M(n) = m with runtime function RunM(n) = t is irreducible if there is not a faster machine F such that F(n) = M(n) for all n and for RunF(n) <= a*log(RunM(n)) for all n larger than some value B and some proportionality constant a.
A Turing machine M's complexity is most commonly discussed in terms of as a set of integers HM = the set of input integers n for which M(n) halts.
By analogy, for a cellular automaton C, we could look at HC = the set of input integers (bitstrings) for which the rule "dies out" in the sense of becoming periodic.
But there are two problems with HC: (a) it's not fine-grained enough, as Rule30 for instance had HC = empty set, so HC doesn't really capture any info about the rule and (b) it's in fact maybe not a computable question to decide when an arbitrary rule has started repeating, as maybe you just haven't waited long enough.
The whole idea of doing a computation with Rule 30 seems impossible, for how would you ever tell it was done? What does the cell line look like when Rule 110 finishes a computation?
In the 1940's Emil Post noticed the question of whether there are sets between Class 1 & 2 and Class 4, and it became called Post's Problem. For a recursion theorists, if you have a set A and a set B, then A <T B if you can answer all questions "is n in A" by using knowledge of what's in B as an "oracle." This is a partial ordering, and the equivalence classes under the ordering are called Turing degrees.
re are two degrees called 0 and 0', which are, respectively the equivalence classes of the recursive sets and the complete oracle for every r.e. set.
New question to worry about. How do you decide if a CA is Class 1, even? Maybe you just haven't waited long enough for it to repeat!
The biggest problem with the PCE is mentioned on p. 734 and the matching footnote. Friedberg Muchnik PROVED that there are non universal but non finite TMs. There isn't any denying it. W's really rather crude experiments (looked at a bunch of CAs) aren't sufficient to distinguish if he's looking at UTM (universal Turing machine) or at some weaker FMM (Friedberg Muchnik machine rule. In the foot note he makes a halfhearted attempt to describe the proof, then says something like "The proof uses a UTM construction so the sophistication of the FMM is really that of a UTM." But this isn't convincing..
Let me think of some analogies.
It's like saying that because Wiles's proof of Fermat’s Last Theorem used hyperbolic geometry, the theorem is independent like Euclid's fifth postulate. Well, not that bad...
It's like someone saying that since Cantor's Diagonal Argument of the uncountability of the Reals involves looking at a countable list of reals, the reals really ARE countable after all. Well, maybe not quite that bad.
It's exactly like saying that since a Cantorian proof of the existence of a transcendental number by diagonalizing over the set of algebraic numbers produces an artificial number and uses the notion of actual infinites, then any transcendental number must be an artificial thing whose existence depends on actual infinities. But of course later Lindemann showed PI is transcendental.
And “it is my strong suspicion” that someone will prove that although Rule 30 is not finitistic or compressible or decidable, it nevertheless codes a computation essentially weaker than that of a UTM. [Well, I don’t' suspect it all that strongly. But it could certainly be.]
The good thing is that this does give Cellular Automatists a new challenge problem: find a CA whose evolution isn't finitely decidable, but which isn't computation universal. I imagine Wolfie (as Bill Gosper calls him) has tried, that little thing in the footnote is probably from an abortive attempt to carry this out. But since he doesn't want the argument to succeed, who's to say that someone with less of a vested interest mightn't carry it off?
Some physicist said once that a great truth is a statement whose negation is also a great truth. I think PCE could be one of those.
Read up on those FMM machines before saying more about them. What on the surface looks bad is for him to say that because the construction of these non-finitistic TMs uses a universal UTM, then there can't in fact be any non finitistic TM that don't somehow involve a UTM. That was my point about transcendental reals. Cantor's proof used a diagonal argument over all algebraics, so you might say the transcendental reals depend on the algebraics, but Lindemann showed Pi is transcendental on its own.
Probably “most” TM have unsolvable halting problems and are not universal.
My SJSU CS colleague Chris Pollett puts it this way. Let’s limited ourselves to a two-symbol alphabet. Suppose that view two Turing machines as identical if they have identical behavior on all inputs (either give same output or fail to halt). For each possible number of allowable states s suppose we let Ts be the total number of s-state Turing machines. Us is the number of universal s-state Turing machines, Hs is the number of s-state TM with solvable halting problem, and Os be the number of other kinds of Turing machines, the intermediate “bad” machines that Wolfram doesn’t want to have around. Ts = Hs + Os + Us. Isn’t is reasonable to suppose that, as s grows large, the ratio Os/Ts will approach 1.0?
Stephen Wolfram is quite cavalier and even denigrating of work in the field loosely known as “chaos.”
I feel that he isn't really giving chaos enough credit.
When discussing chaos, W continually harks back to the fact that the shift map x = 2 x MOD 1.0 excavates the random digits in a real, but doesn’t introduce complex behavior. He points out that, on the other hand, x = 1.5 x MOD 1.0 does introduce complexity.
1) Why does chaos produce fractal strange attractors? Wolfram seems to dismiss chaos as being “about” excavating initial conditions. But it’s the behavior of an ensemble of initial conditions that’s interesting, in which case the sensitive dependence on initial conditions isn’t really the point. The point is that, with something like a Yorke attractor, we have the ensemble doing something interesting. A random cloud of starting points converges upon a fractal attractor. Is there a way to recast this into Wolfram’s terms.
Let’s think of his “generalized mobile automata” on p. 78. The idea I want to use is that of multiple moving computation heads that don’t themselves have internal state (unlike Turing Machine heads). We divide a unit square into a grid, assigning a real number coordinate pair to each grid site in the most natural way, and place a head into each cell. Each cell holds its real number coordinate pair plus an integer hitcount. The hitcounts are initially all 0.
The update rule for a head is to (a) increment the hitcount in its current cell and (b) read the coordinates (x, y) of the current cell, compute new coordinates (x*, y*) = H(x, y) and move the head to the cell with coordinates (x*, y*).
(To reduce the role of sensitive dependence on initial conditions, we can round off (x*, y*) to match the coordinates of the cell it lands in. See the Pendulum and Magnets discussion below.)
We classify the rules according to the pattern of hitcounts that we see. They can all be (1) repetitive in the sense of being at one spot, in stripes or checkers, or (2) they can be in an orderly nested pattern or (3) or they can smeared be all over the place, (4) or they can be like veins of fractal marble, nested but not in an orderly way.
Woud be interesting to try a lot of very simple maps H(x, y), like, say bilinear maps given by a, b, c, d such as x* = ax + by MOD 1, etc. I think there was in fact some study of these in a Dewdney column, the rule was called Hopalong? Following Wolfram, we might ask if bilinear is the simplest thing to give interesting behavior? How about a pair of shift maps. We cross the variables over so that x and y interact. Should try this with various values of a and b and see if we can get the four classes this way.
x* = ay MOD 1
y* = b x MOD 1
Something not quite satisfying about the strange attractor computations is that they don’t seem to keep generating new pretty pictures, that is, after you run the rule for a few hundred or thousand steps, all the computing heads are “on” the strange attractor, if there is one, and they just keep dancing around on it. Well, I guess some class 4 CAs do things sort of like that.
How does the role of zooming fit in here? In a world with no regard for computational resources, we could have each head and all the cells split into four every so often. Could do it at every step, but if I wanted to be practical, it would be better to split after a few hundred steps. So then you’d have all the heads on the attractor more or less, and you’d split (x, y) into (x+-d, y+-d) or something like that.
The Mandelbrot set is more complicated than the simple strange attractor maps just discussed because starting from each point c = (x, y) we use a different map (x*, y*) = Hc(x, y). It doesn’t make as much sense to talk of moving heads here, as the computation starts at a given point, and the color it computes will be shown at that same point. I guess you could say you have static computing heads — like in a CA.
In both the Mandelbrot set and the strange attractor, you might say these aren’t like CAs because they don’t look at neighborhood information. They’re not even like Turing machines because they don’t read states off a tape. But in a weaker sense they read from the neighborhood they find themselves in, that is, they read the coordinates. It’s just that the coordinates in the world don’t change.
We divide a rectangle into a grid, assigning a real number coordinate pair (or a complex number if you like) to each grid site in the most natural way, and place a head into each cell. Each cell holds its real number coordinate pair plus an integer escapecount. The escapecount are initially all some large integer BIGNUM.
For the M-set, we put a computing head at each cell. Each head holds a real pair c a real pair o and an integer i. We initialize c to the current (x, y) location and i to 0. We repeat these operations at each cell.
o = o^2 + c;
i++;
if (cell.escapecount == BIGNUM && norm(o) > 2.1) cell.escapecount = i;
After each update set each cell’s color to match its current escapecount. Ordinarily we use black for the BIGNUM value of escape count. What you will see is a black screen with first a band of red (let’s just arbitrarily use the spectrum for the first few colors) around the edge, then a band of yellow inside that, a band of green inside that, and so on. One new band appears per update for awhile, but eventually it may take many updates before you see evidence of another band, also after awhile the bands won’t be connected, indeed they’ll eventually just be isolated dustings of pixels.
Is the computation “wasted” once cell.escapecount gets set? It would seem so. So you could either have the head stop doing anything, or what we might instead do would be to send that head off to a new refinement of some cell’s location. That is, think of the heads that have finished a band as always moving to a refinement of a boundary cell between two bands. Or have them want to migrate especially to the zones where the computation isn’t done yet.
I’ve never seen a Mandelbrot set computation done in this parallel fashion, it would be fun to watch.
Another relevant thing here might be to look at this in 3D, think of us as stacking up successive computation planes of the M-set.
Might it after all be worthwhile to look at the orbits of the computing heads o locations? Conventional wisdom is that every orbit either repeats or rushes out to infinity. But I guess there is a zero measure set of orbits, those on the impossible rim of the set, which in fact do a chaotic dance on the strange attractor.
It seems like a frictionless pendulum over a set of magnets is performing some kind of computation. We essentially have an iterated map p* = H(p) in the plane. The variable initial condition is the bob location at start, also there are some “fixed” initial conditions (positions of the magnets) that specify H.
In time, an individual orbit will be sensitive to the initial and fixed initial conditions, which is something W doesn’t like. The initial conditions will dominate the long term behavior. Unless maybe we have some friction and a driving force.
Still, the jiggling and dancing of the pendulum head certainly makes me think of a Type Four CA glider darting back and forth. Why not throw out all but, say, five decimals of the position and velocity information at each step. Then your sensitivity is gone. You’re no longer excavating initial conditions. But you still have complex behavior. Yes!
A really essential thing about how we experience strange attractors and the Mandelbrot set is that we zoom in on them.
There’s a sense in which watching a 1D CA (without wrapping) is a zoom. You keep growing the size of the array you look at, even though you are showing less and less of it.
If I zoom on an attractor, I in fact have to maintain a much larger space than I show, as the orbit values will continue to dance all over the space. But this is, again, no different from tracking a particular glider in, say Rule 110.
And picking the point to zoom on is very much like picking the initial condition of a CA. In a CA you put a seed pattern into the line and center the line with a particular location in the center of your screen. And the pattern grows. Over time your screen becomes a more and more “zoomed in” portion of the total output you are computing.
So we might view a Mandelbrot set computation in the following form. You are stacking up zoom sheets. Some locations lead to interesting things (if they’re at the border) others don’t.
How to blend the zoom stack with the computation stack I described above? The smoothest would be to expand the frame so slowly that you only lose one line of pixels around the edge with each update. But that would be a mess, computationally.
How about this, whenever a “head” escapes, then you split that head into four and start over. Unless there’s a way to see that nothing more is gonna happen there.
There’s a lot more to be said and done in this area. See my papers on the topic, also the Kaneko work that Wolfram mentions.