Jason Cawley
Wolfram Science Group
Phoenix, AZ USA
Registered: Aug 2003
Posts: 712 
Simple NKS questions for SAT style tests
At this year's summer program at Brown, we considered ways of furthering NKS in education. One idea I had was to smuggle in NKS considerations through standardized tests, given the manner in which teachers and students these days focus on such tests. NKS seems to lend itself to such questions, which should not require previous familiarity with the subject, and should be readily answered, accurately by any decent student, in less than a minute. I thought others here might have some ideas for simple questions along these lines.
Here are some sample subjects 
Following finite state machine transitions
Composing transformation steps
Noticing cycles or necessary end states in FSMs
"Recoding" a FSM
e.g. states 1,2,3 are called A, states 4, 5 are called B,
give the AB sequence this FSM follows starting at 2.
FSM rules given in English.
There are some very simple exercises like this early in Ashby.
Also sSimple substitution system questions, followed for just 1, 2, 3 steps.
Slightly harder ones, e.g. can you reach string xxxx from yyy using rules a b c, where there is a simple trick.
Filling in a pair of blank squares in a CA given the entire rule (pair used to get 4 multiple choice outcomes).
Filling in a pair of blank squares in a CA given only the pattern (where one must notice the rule  given its form, though). Simple rule cases.
Sequence questions, like how many steps does 3n+1 take to get to 1 starting from this number or that number  relatively easy cases.
Matthew Szudzik suggested the following substitution system questions 
(1) Using the substitution rules
0 > 00
0 > 11
1100 > 01
can 00 be transformed into 111?
Solution: Yes, 00 > 000 > 1100 > 01 > 111.
This example comes from page 776 of the NKS book.
(2) Using the substitution rules
1 > 010
001 > 1
11 > 0
can 101 be transformed into 01110?
Solution: No, the rules can never increase the number of 1's in a
sequence.
(3) Using the substitution rules
0 > 001
10 > 011
0011 > 101
can 0100 be transformed into 101?
Solution: No. Starting from 101 and following the rules backwards we see that there are only three possible sequences that can be transformed into 101, namely 0011, 010, and 01.
Note that I chose to use 0's and 1's instead of A's and B's to avoid confusion, since standardized tests like the SAT usually assign the letters A, B, C, etc. to potential answers.
Matthew Szudzik
Here are some Ashby like questions about simple transformation rules 
A transformation is a list of rules that say what each starting state, marked as some letter, goes to next, written as e.g. 
A: a > c, b > c, c > a
A composition or
product of two transformations is simply the result of applying each individual transformation in sequence.
If A is as given above, what is the transformation A A = A ^ 2?
(1) A^2 : a > a, b > a, c> c
(2) A^2: a>c, b > c, c>c
(3) A^2: a>e, b>d, c>a
(4) A^2: a>c, b>a, c>c
Which of the following is A^4? (...)
If A is as above and B is B: a>b, b>c, c>a, then which of the following is the transformation B A B? (...)
It seems to me there is a fine opportunity here to smuggle NKS style thinking into the curriculum. Anyone can answer such simple questions without ever having seen them before, but students will prefer to have seen them before, in the interest of testing speed among other things.
Report this post to a moderator  IP: Logged
