Unary Functions

Dr. Todd Rowland
todd_rowland@wolfram.com
Wolfram Science Group
http://www.wolframscience.com/reference/education/

Description

This lesson introduces the idea of a rule which, on each step, changes every bit in a string. The rules investigated in this lesson only depend on the value of the bit being changed. And none of its neighbors.

Pre - requisites:

Introduction to Digital Information

Objectives

Materials:

Graph paper

 Computers

Further Notes:

From NCTM  http://www.nctm.org/standards/

What is the value of a bit after the Not operator is applied n times?   Answer can be given in terms of odd and even...

What are the functions in this lesson?  We get periodic behavior with the Not operator.  The other functions ultimately constant, including the identity function.

Conjecture  a description of one of these operators, and prove your conjecture.  Test conjecture.  Use answer to determine when n = 1, 2, 3, ...

Background:

We now begin our investigation of simple programs, which we call rules. These rules provide us with the means to change the bits of a string.

On each step, a rule operates on every bit in the string.  The simplest type of rule is where each bit gets changed depending on its value.

One of these rules plays an important role in logic and in computer programming.  It is called the "Not" operator.  Where you see a zero, replace it with a one.  Vice versa, where you see a one replace it with a zero.

In addition to the Not operator, described above, there are three further possible rules that are unary functions. One turns any string into a string of zero's.  Another turns any string into a string of one's.  The last one is the identity operator, which causes no changes. Not only does each of the four possible rules have a distinct description, but it pehaves differently aslo.  One is cyclic with period two, which means that you get the same thing back every two steps. The other three have finite evolutions, meaning they stop changing after a finite number of steps.

Procedure:

"Not" Rule

Graphical representation of our string :

Let us apply the rule for 1 step :

The graphical representation makes it easier for the reader to "perceive" what the rule does ....

Black cells turn to white cells and white cells turn to black cells.

Let us apply the rule for a further step:

Can you see a repetition arising ?  What would you expect step 4 to look like?

What does step 7 look like ?

Comment:

This rule seems to exhibit cyclic behavior; it repeats itself after 2 steps.

Identity Rule

What does the following rule do to our initial condition ?

This rule says that a black cell remains black and a white cell remains white.  So, can we generalize what step 2, step 3 and all its consecutives will look like?

Comment:

This rule exhibits constant behavior

Questions:

Assessment:

Answer:

({{1.  Possiblity, 0 -> 0, 1 -> 0}, {2.  Possibility, 0 -> 0, 1 -> 1}, {3.  Possibility, 0 -> 1, 1 -> 0}, {4.  Possibilty, 0 -> 1, 1 -> 1}})