Home What's Up? NKS Dates Call for Papers Conference Program Submit Paper Register Sponsors Contact Travel Local Arrangements


Friday (Oct. 28, 2005)
Saturday (Oct. 29, 2005)
Sunday (Oct. 30, 2005)

Continental Breakfast

Coffee Service
  Veerman, Bustamante, Guerra Dag Sørebø
  Enrique Zeleny Wendy Zhang
  Kovas Boguta Paul-Jean Letourneau


  Ed Pegg Jr. (Demoscene)
  Michael Round

Closing Address:
Todd Rowland

Distinguished Invited Talk
(IMU Coronation Room)

  Robert de Marrais

Prof. Jonathan Mills
Lunch (w/ Plenary Presenter)

(IMU Frangipani)

  Conference Ends.

Registration Check-in
(Conference Lounge)

Matthew Frank  
Brenton Bostick
Jason Cawley

First Keynote Speaker:
Matthew Szudzik (CMU)

Colloquium in Lindley 102

Prof. Ray J. Solomonoff
Distinguished Invited Lecture


Dinner (in Bloomington).
Also in Frangipani.



Welcome Address:
Prof. Mike Dunn, Dean
IU School of Informatics

Opening Reception
(IMU State Room East)


Stephen Wolfram

(IMU Frangipani link to Boston)

George E. Danner  
B. McGarry, D. Gage, E. Laub  
Eric Rowland

Round-table Discussion:

Late night pizza and refreshments. Positional Number Systems
with Negative Digits and NKS

Late night pizza and refreshments.





Keynote Speakers:

Prof. J. Michael Dunn
Oscar R. Ewing Professor of Philosophy
Dean of Indiana University School of Informatics
18:30 Friday (IMU State Room East)
Conference Welcome Address

Stephen Wolfram (Selected Talks and Presentations)
Creator of Mathematica.
Author of A New Kind of Science
CEO of Wolfram Research, Inc.
20:00 Saturday (in direct to Frangipani via videolink from Boston)
Conference Keynote Address

This will be a fully interactive event (bidirectional video link).

Prof. Ray J. Solomonoff (Selected Talks and Publications)
Founder of Algorithmic Probability Theory
Founder of Universal Theory of Inductive Inference
16:00 Saturday (IMU Dogwood)
Distinguished Invited Lecture on Algorithmic Probability, AI and NKS.


Matthew Szudzik
Carnegie Mellon University
Doctoral Candidate in Mathematical Logic
Former Research Assistant to Stephen Wolfram (1998-2000, 2001)
NKS Summer School Instructor (since 2003)
16:00 Friday (LH102 or Informatics 107 or the Georgian Room)
First Keynote Address (as part of IUB Informatics Colloquium Series)


Todd Rowland
Ph. D. in Mathematics (Univ. of Chicago, 1999)
Senior Research Associate with Wolfram Research, Inc.
Managing Editor of the Complex Systems Journal
11:30 Sunday (IMU Dogwood or Coronation Room)
Conference Closing Keynote Address

Prof. Jonathan Mills
Professor of Computer Science
Inventor of Łukasiewicz Logic Arrays
Indiana University Department of Computer Science
12:30 Saturday (IMU Frangipani)
Analog Computers and Computations on the Continuum


Individual Presentations:

Applying NKS to Real World Problems: A Journey Without End (21:00, Friday)
George E. Danner (Industrial Science, LLC)

The "simple program" perspective of A New Kind of Science (NKS) promises to shed light on a wide range of complex problems. Yet therein lays the challenge: which problems are suitable for an NKS approach? How should we think through the application of NKS to a real world problem? This paper offers a discussion on this topic, centered around the creation of stylized problem forms in much the same manner that the famous Traveling Salesman Problem (TSP) was used to advance both research and application in the Operations research community. There perhaps exists such a class of stylized problem that will be of interest to both sides of the NKS community as well. We take the reader through a journey to understand the behavior of NKS-based solutions to the Easter Egg Problem (EEP), a proposed problem form with distinct features, common to observed problems in the real world.


Cellular Automata: Is Rule 30 Random? (21:30, Friday)
Briana McGarry (Central Michigan University)
Dustin Gage (University of Maine at Farmington)
Elizabeth Laub (Susquhanna University)

PDF version of this paper can be accessed here.

Dr. Stephen Wolfram, developer of Mathematica, claims that Rule 30 can be used as an effective encryption scheme due to its random qualities. We investigate this claim using programs that produce different aspects of the Rule's output. From these programs, we were able to create a battery of statistical tests as well as identify properties that help characterize its security if used for encryption. The results provide adequate randomness for a high level of security with weaknesses isolated to even window sizes.


The Right Side of Rule 30 (22:00, Friday)
Eric Rowland (Rutgers University, Dept. of Mathematics)

By "rule 30*" we will mean "rule 30 begun from a single black cell". An observation that has not been previously emphasized is that rule 30* displays a sort of nested structure on the right side. Specifically, row 2^n ends in a single black cell preceded by a sequence of white cells. This causes the computation of rule 30* to "begin again" at row 2^n and continue for a number of rows before being influenced by the rest of the black structure. This nested structure gives rise to a new integer sequence. Let L(t) be the length of the maximal rightmost sequence of black cells on row t of rule 30*. The sequence {L(t)} begins 1, 3, 1, 4, 1, 3, 1, 6, 1, 3, 1, 4, 1, 3, 1, 7, ... and has the structure of {IntegerExponent[t + 1, 2]}, with new entries occurring at positions 2^n - 1. The sequence of distinct entries begins 1, 3, 4, 6, 7, 9, 15, 16, 24, 25, 27, 29, ... (and, expectedly, seems to exhibit complex behavior). The nested structure is not unique to rule 30; it is found on the right side of sixteen elementary cellular automata, including the "nested" rules 60, 90, 105, 150, 225 (for which this is not surprising) as well as the "class 3" rules 45 and 75. In general, the property that guarantees such a nested structure for a rule is one-sided additivity. It happens that, under certain conditions, this property also guarantees existence and uniqueness of a predecessor to a row. We prove a general theorem regarding the nested structure in a k-color cellular automaton with one-sided additivity. We then use this theorem to show that the sequence {L(t)} is unbounded.


Two methods for finding cellular automata that perform simple computations. (9:00, Saturday)
Johan Veerman, Mauricio Bustamante, Cesar Guerra (Pontificia Universidad Católica del Perú)

We have used two different methods to find cellular automata (CA) that perform some simple computations: by specifically constructing them to do a certain task and by doing searches in CA rule space. For the first case (specific construction), we start by building a CA that computes some arithmetical or logical function in a serial way, that is, a particle first moves to read one of the inputs and then applies it to the other one. Even though the rule you find ends up with a lot of states, depending on the type of operation you want it to perform, and it is not simple anymore, we find some types of behavior that are then used to construct CA rules that perform the same tasks but in a parallel way, therefore requiring a fewer number of states and steps. The results obtained in the first method are then used as restrictions or assumptions for the second method (searches in a rule space) in order to narrow down the rule space to perform a more directed search. We show some results for arithmetical functions, bitwise logical operations and other simple computations.

Poster presentation (presenters won't be able to make it to Bloomington for the conference).

Generalizing Recursive Sequences (9:30, Saturday)
Enrique Zeleny (Universidad Autónoma de Puebla, Mexico)

I will show what happens with recursive sequences when initial values are changed or added, and whose behavior can be described with some simple program or formula and a systematic study of how often the RS gets undefined. Next, we can see how a RW can be emulated with subtitution system. Studying what happens in the process of evaluation, looking the number of intermediate steps and the values visited in each recursion is interesting too, and trying to find some connections with symbolic systems. I have some examples of RS defined for rational arguments.

This presentation was canceled because Enrique forgot to bring his laptop, and none of the existing laptops matched what he needed.

Nested Recursive Sequences (10:00, Saturday)
Kovas Boguta

The famous Hofstadter Q sequence is generated by the function f(n) = f(n - f(n - 1)) + f(n - f(n - 2))), with f(1) = f(2) = 1. We introduce and experimentally investigate the general class of such functions, called Nested Recursive Functions, whose simplest members take the form f(n) = a f(n - b f(n - c)). Despite their simple definition, they achieve a wide range of dynamics with different choices of the parameters a, b, and c. We classify typical behaviors, introduce methods of analysis, and establish theorems for computationally reducible cases.

Demoscene: Making Movies from Simple Programs (11:00, Saturday)
Ed Pegg, Jr.

What applications use simple programs? One area they are used effectively is the world of Demoscene competitions, where a spectacular movie of some sort must be made under incredible constraints. This talk will survey some of the more spectacular examples from this realm, and discuss some of the techniques.

Two-dimensional Cellular-Automata, Systems, and Inherent Simplicity (11:30, Saturday)
Michael Round

Our fascination with snowflakes usually ends after a brief period of marvel upon unfolding a folded-and-cut paper revealing beauty and symmetry. This lost opportunity on math and science education is made worse in that the wrong idea of the generation of a snowflake is communicated with such a "pedagogic" process. The Thinking Processes of the Theory of Constraints for Education will be used to demonstrate a unique and powerful method of understanding NKS snowflake growth, snowflake variation, random and fixed initial conditions, and underlying assumptions giving rise to snowflake complexity under differing environmental conditions. Additionally, a model for exploring necessary and sufficient conditions of snowflake growth will be discussed. A rational construction of models, experimentation, logic, simulation, the verbalization of assumptions, and a structured approach to independent research will be demonstrated in this presentation.

Presto! Digitization: From NKS Number Theory to "XORbitant" Semantics,
by way of Cayley-Dickson Process and Zero-Divisor-based "Representations"

Robert de Marrais (12:00, Saturday)

The objects of the great Nonlinear Revolutions – Catastrophes and Chaos in the 1960s-70s (henceforth, CT); and, “small-world” and “scale-free” Network Theory (NT), emerging from studies of synchronization since the Millennium – will be spliced together by a New Kind of Number Theory, focused on digitizations (i.e., binary strings). NT nodes then become "feature-rich" representations (nodules in a “rhizosphere”) of CT contents.

The "Box-Kite" formalism of zero divisors (ZD's) – first showing in the 16-D Sedenions, then in all higher 2N-ions derived from Imaginaries by Cayley-Dickson Process (CDP) – can model such “enriched” nodules. Its (bit-string XOR-ing vs. matrix-multiplication-based) operations unfold into "representations" of the objects traditionally linked with “partitions of Nullity”: Singularities. The route from this “local” level of CT to fractals and Chaos, via CDP extensions to 2N-ions for growing N, will involve us in graphics of higher-dimensional “carry-bit overflow,” as manifest in the mandala-like patterns showing up in “emanation tables” (the rough equivalent, for ZD's, of group theorists' Cayley Tables). More concretely, this route will model semantic propagation – “meaning” itself.

I'll lead into this with a quote about "Hjelmslev's Net" (which I'll claim is the CDP manqué) from a famous postmodern text deeply engaged with the philosophy of future mathematics, Deleuze and Guattari's A Thousand Plateaus (where “rhizosphere” imagery arose). From here, with strong assists from the CT-based structuralism of Jean Petitot, Algirdas Greimas's “Semiotic Square” will show us how to explicitly link CT thinking to the foundations of semantics via ZD “representations,” while the infinite-dimensional ZD meta-fractal or “Sky” which Box-Kites fly “beneath” or “in” – first appearing in the 32-D Pathions and incorporating the higher 2N-ions – will provide sufficient lebensraum for Lévi-Strauss's “Canonical Formula” of mythwork to unfurl in, thereby doing for semiotics what S-matrix methods promised for particle physics. (These results serve to extend my NKS 2004 paper.)

An NKS Approach to the Black-Scholes Equation. (14:00, Saturday)
Matthew Frank (Goldman-Sachs)

Discretization is a hallmark of the approach in A New Kind Of Science. I explore some implications of this in financial mathematics, starting with the Black-Scholes equation and formulas. Specifically, I report on some numerical experiments following the work of Leland (1985) on 'Option Pricing and Replication with Transaction Costs'.

The 3n+1 Problem: Variations on a Theme (14:30, Saturday)
Brenton Bostick

The 3n+1 Problem is a famous problem in mathematics that demonstrates the idea of simple inputs into a system causing very complex output. An efficient cellular automaton that emulates the 3n+1 function is demonstrated. Structures that appear in the cellular automaton are discussed. Variations of the cellular automaton are then introduced, where they are compared with various mathematical functions.

Markov Machines
Jason Cawley (15:00, Saturday)

Thinking security with NKS-awareness
Dag Sørebø (9:00, Sunday)

Multiscale Simulation of Avian Limb Development
Wendy Zhang (9:30, Sunday)

Cellular Automata with Memory: Phenomena and Emulations
Paul-Jean Letourneau (10:00, Sunday)


Round table organizers:

A. German, T. Sato, J. Bonner, K. Nagao, A. M. Martin and Y. Yamamoto (22:00, Saturday)
Positional Number Systems with Negative Digits in Algorithmic Information Theory and NKS

This presentation was canceled. There was no time for it on Saturday night.