WolframAlpha.com
WolframCloud.com
All Sites & Public Resources...
Products & Services
Wolfram|One
Mathematica
Wolfram|Alpha Notebook Edition
Finance Platform
System Modeler
Wolfram Player
Wolfram Engine
WolframScript
Enterprise Private Cloud
Application Server
Enterprise Mathematica
Wolfram|Alpha Appliance
Enterprise Solutions
Corporate Consulting
Technical Consulting
Wolfram|Alpha Business Solutions
Resource System
Data Repository
Neural Net Repository
Function Repository
Wolfram|Alpha
Wolfram|Alpha Pro
Problem Generator
API
Data Drop
Products for Education
Mobile Apps
Wolfram Player
Wolfram Cloud App
Wolfram|Alpha for Mobile
Wolfram|Alpha-Powered Apps
Services
Paid Project Support
Wolfram U
Summer Programs
All Products & Services »
Technologies
Wolfram Language
Revolutionary knowledge-based programming language.
Wolfram Cloud
Central infrastructure for Wolfram's cloud products & services.
Wolfram Science
Technology-enabling science of the computational universe.
Wolfram Notebooks
The preeminent environment for any technical workflows.
Wolfram Engine
Software engine implementing the Wolfram Language.
Wolfram Natural Language Understanding System
Knowledge-based broadly deployed natural language.
Wolfram Data Framework
Semantic framework for real-world data.
Wolfram Universal Deployment System
Instant deployment across cloud, desktop, mobile, and more.
Wolfram Knowledgebase
Curated computable knowledge powering Wolfram|Alpha.
All Technologies »
Solutions
Engineering, R&D
Aerospace & Defense
Chemical Engineering
Control Systems
Electrical Engineering
Image Processing
Industrial Engineering
Mechanical Engineering
Operations Research
More...
Finance, Statistics & Business Analysis
Actuarial Sciences
Bioinformatics
Data Science
Econometrics
Financial Risk Management
Statistics
More...
Education
All Solutions for Education
Trends
Machine Learning
Multiparadigm Data Science
Internet of Things
High-Performance Computing
Hackathons
Software & Web
Software Development
Authoring & Publishing
Interface Development
Web Development
Sciences
Astronomy
Biology
Chemistry
More...
All Solutions »
Learning & Support
Learning
Wolfram Language Documentation
Fast Introduction for Programmers
Wolfram U
Videos & Screencasts
Wolfram Language Introductory Book
Webinars & Training
Summer Programs
Books
Need Help?
Support FAQ
Wolfram Community
Contact Support
Premium Support
Paid Project Support
Technical Consulting
All Learning & Support »
Company
About
Company Background
Wolfram Blog
Events
Contact Us
Work with Us
Careers at Wolfram
Internships
Other Wolfram Language Jobs
Initiatives
Wolfram Foundation
MathWorld
Computer-Based Math
A New Kind of Science
Wolfram Technology for Hackathons
Student Ambassador Program
Wolfram for Startups
Demonstrations Project
Wolfram Innovator Awards
Wolfram + Raspberry Pi
Summer Programs
More...
All Company »
Search
WOLFRAM COMMUNITY
Connect with users of Wolfram technologies to learn, solve problems and share ideas
Join
Sign In
Dashboard
Groups
People
Message Boards
Answer
(
Unmark
)
Mark as an Answer
GROUPS:
Staff Picks
Wolfram Science
Computer Science
Graphics and Visualization
Wolfram Language
Wolfram High School Summer Camp
3
Samikshaa Natarajan
[WSC21] Implementing counter machines
Samikshaa Natarajan
Posted
1 year ago
2726 Views
|
2 Replies
|
3 Total Likes
Follow this post
|
Implementing counter machines
by
Sam Natarajan
The objective of this project was to implement counter machines in the Wolfram Language and establish which counter machine was the most unpredictable. I designed a general counter machine function and used this function to demonstrate 5 types of counter machines. Finally, I determined which counter machines were unpredictable and explored complexity by adding more registers.
An Introduction to Counter Machines
Counter machines operate on a list of numbers based off a set of instructions. They have multiple registers, or slots, each of which holds a single non-negative integer. In this project, the main focus is counter machines with two registers, but three-register counter machines are analyzed as well. Each type of counter machine has a defined set of instructions, and the counter machine executes these instructions on the registers. There are many different types of counter machines, characterized by their instruction sets.
Each instruction for a counter machine references an operator, such as increment (
inc
), decrement (
dec
), and jump (
j
).
Show an example of a counter machine instruction set:
I
n
[
]
:
=
{
i
n
c
[
r
1
]
,
d
e
c
[
r
2
]
,
j
[
1
]
}
;
These operators change the values of each register and/or the current instruction. There are approximately 10 operators: 5 are standard operators and the rest are conditional operators. Most counter machine instructions reference a couple standard operators and one conditional operator.
Creating a Counter Machine Function
I
n
[
]
:
=
Creating and Running a Counter Machine
A counter machine is expressed in the form
{z, {r1, r2, r3 ...}}
. The first item,
z,
represents the current instruction the counter machine is evaluating, and
{r1, r2, r3...}
are the registers. Using this information, one can create a generic counter machine using
Table
, shown in the code below.
Create an empty counter machine with Table:
I
n
[
]
:
=
c
o
u
n
t
e
r
M
a
c
h
i
n
e
[
n
_
I
n
t
e
g
e
r
]
:
=
{
1
,
T
a
b
l
e
[
0
,
n
]
}
;
In Stephen Wolfram's book,
A New Kind of Science
, he writes the following two functions to run a generic counter machine.
Evolve a counter machine by nesting steps from an instruction set:
I
n
[
]
:
=
c
m
E
v
o
l
v
e
L
i
s
t
[
p
r
o
g
r
a
m
_
,
i
n
i
t
:
{
_
I
n
t
e
g
e
r
,
_
L
i
s
t
}
,
t
_
I
n
t
e
g
e
r
]
:
=
N
e
s
t
L
i
s
t
[
c
m
S
t
e
p
[
p
r
o
g
r
a
m
,
#
]
&
,
i
n
i
t
,
t
]
c
m
S
t
e
p
[
p
r
o
g
r
a
m
_
,
{
n
_
I
n
t
e
g
e
r
,
l
i
s
t
_
L
i
s
t
}
]
:
=
I
f
[
n
>
L
e
n
g
t
h
[
p
r
o
g
r
a
m
]
,
{
1
,
l
i
s
t
}
,
c
m
E
x
e
c
u
t
e
[
p
r
o
g
r
a
m
[
[
n
]
]
,
{
n
,
l
i
s
t
}
]
]
Given a list of instructions, an initial counter machine, and the number of times to run the counter machine, the first function above utilizes a
NestList
to run the counter machine. The second function runs each individual iteration of the counter machine. If the current instruction is beyond the amount of instructions provided, the current instruction
z
resets to 1; otherwise, the function executes the current instruction.
I
n
[
]
:
=
Counter Machine Operators
Each instruction references a counter machine operator. There are many operators for counter machines; each is explained below with its code.
Increment (INC) - Increase the value of register
r
by 1:
I
n
[
]
:
=
c
m
E
x
e
c
u
t
e
[
i
n
c
[
r
_
,
z
_
]
,
{
n
_
,
l
i
s
t
_
}
]
:
=
{
z
,
M
a
p
A
t
[
(
#
+
1
)
&
,
l
i
s
t
,
r
]
}
c
m
E
x
e
c
u
t
e
[
i
n
c
[
r
_
]
,
{
n
_
,
l
i
s
t
_
}
]
:
=
c
m
E
x
e
c
u
t
e
[
i
n
c
[
r
,
(
n
+
1
)
]
,
{
n
,
l
i
s
t
}
]
◼
The first increment function has the next instruction explicitly specified.
◼
The second increment function simply goes to the next instruction.
Decrement (DEC) - Decrease the value of register
r
by 1:
I
n
[
]
:
=
c
m
E
x
e
c
u
t
e
[
d
e
c
[
r
_
,
z
_
]
,
{
n
_
,
l
i
s
t
_
}
]
:
=
I
f
[
l
i
s
t
[
[
r
]
]
≤
0
,
{
n
+
1
,
l
i
s
t
}
,
{
z
,
M
a
p
A
t
[
(
#
-
1
)
&
,
l
i
s
t
,
r
]
}
]
c
m
E
x
e
c
u
t
e
[
d
e
c
[
r
_
]
,
{
n
_
,
l
i
s
t
_
}
]
:
=
c
m
E
x
e
c
u
t
e
[
d
e
c
[
r
,
(
n
+
1
)
]
,
{
n
,
l
i
s
t
}
]
◼
The first decrement function has the next instruction explicitly specified.
◼
The second decrement function simply goes to the next instruction.
Clear (CLR) - Set register
r
to 0:
I
n
[
]
:
=
c
m
E
x
e
c
u
t
e
[
c
l
r
[
r
_
]
,
{
n
_
,
l
i
s
t
_
}
]
:
=
{
n
+
1
,
M
a
p
A
t
[
0
&
,
l
i
s
t
,
r
]
}
Copy (CPY) - Copy the value of register
r1
to register
r2
:
I
n
[
]
:
=
c
m
E
x
e
c
u
t
e
[
c
p
y
[
r
1
_
,
r
2
_
]
,
{
n
_
,
l
i
s
t
_
}
]
:
=
{
n
+
1
,
M
a
p
A
t
[
l
i
s
t
[
[
r
1
]
]
&
,
l
i
s
t
,
r
2
]
}
Jump (J) - Jump to instruction
z
:
I
n
[
]
:
=
c
m
E
x
e
c
u
t
e
[
j
[
z
_
]
,
{
n
_
,
l
i
s
t
_
}
]
:
=
{
z
,
l
i
s
t
}
Jump if Zero (JZ) - If the value in register
r
is 0, then jump to instruction
z
; otherwise continue to the next instruction:
I
n
[
]
:
=
c
m
E
x
e
c
u
t
e
[
j
z
[
r
_
,
z
T
r
u
e
_
,
z
F
a
l
s
e
_
]
,
{
n
_
,
l
i
s
t
_
}
]
:
=
I
f
[
l
i
s
t
[
[
r
]
]
0
,
{
z
T
r
u
e
,
l
i
s
t
}
,
{
z
F
a
l
s
e
,
l
i
s
t
}
]
Jump if Not Zero (JNZ) - If the value in register
r
is not 0, then jump to instruction
z
; otherwise continue to the next instruction:
I
n
[
]
:
=
c
m
E
x
e
c
u
t
e
[
j
n
z
[
r
_
,
z
T
r
u
e
_
,
z
F
a
l
s
e
_
]
,
{
n
_
,
l
i
s
t
_
}
]
:
=
I
f
[
l
i
s
t
[
[
r
]
]
≠
0
,
{
z
T
r
u
e
,
l
i
s
t
}
,
{
z
F
a
l
s
e
,
l
i
s
t
}
]
Jump if Zero or Decrement (JZDEC) - If the value in register
r
is 0, then jump to instruction
z
; otherwise decrement the value in register
r:
I
n
[
]
:
=
c
m
E
x
e
c
u
t
e
[
j
z
d
e
c
[
r
_
,
z
T
r
u
e
_
,
z
F
a
l
s
e
_
]
,
{
n
_
,
l
i
s
t
_
}
]
:
=
I
f
[
l
i
s
t
[
[
r
]
]
0
,
{
z
T
r
u
e
,
l
i
s
t
}
,
c
m
E
x
e
c
u
t
e
[
d
e
c
[
r
,
z
F
a
l
s
e
]
,
{
n
,
l
i
s
t
}
]
]
Jump if Equal (JE) - If the value in register
r1
is equal to the value in register
r2
, then jump to instruction
z
; otherwise continue to the next instruction:
I
n
[
]
:
=
c
m
E
x
e
c
u
t
e
[
j
e
[
r
1
_
,
r
2
_
,
z
T
r
u
e
_
,
z
F
a
l
s
e
_
]
,
{
n
_
,
l
i
s
t
_
}
]
:
=
I
f
[
l
i
s
t
[
[
r
1
]
]
l
i
s
t
[
[
r
2
]
]
,
{
z
T
r
u
e
,
l
i
s
t
}
,
{
z
F
a
l
s
e
,
l
i
s
t
}
]
I
n
[
]
:
=
Final Counter Machine Function
Putting all these functions together creates a generic counter machine function.
Create the final counter machine function:
I
n
[
]
:
=
c
o
u
n
t
e
r
M
a
c
h
i
n
e
[
n
_
I
n
t
e
g
e
r
]
:
=
{
1
,
T
a
b
l
e
[
0
,
n
]
}
;
c
m
E
v
o
l
v
e
L
i
s
t
[
p
r
o
g
r
a
m
_
,
i
n
i
t
:
{
_
I
n
t
e
g
e
r
,
_
L
i
s
t
}
,
t
_
I
n
t
e
g
e
r
]
:
=
N
e
s
t
L
i
s
t
[
c
m
S
t
e
p
[
p
r
o
g
r
a
m
,
#
]
&
,
i
n
i
t
,
t
]
c
m
S
t
e
p
[
p
r
o
g
r
a
m
_
,
{
n
_
I
n
t
e
g
e
r
,
l
i
s
t
_
L
i
s
t
}
]
:
=
I
f
[
n
>
L
e
n
g
t
h
[
p
r
o
g
r
a
m
]
,
{
1
,
l
i
s
t
}
,
c
m
E
x
e
c
u
t
e
[
p
r
o
g
r
a
m
[
[
n
]
]
,
{
n
,
l
i
s
t
}
]
]
c
m
E
x
e
c
u
t
e
[
i
n
c
[
r
_
,
z
_
]
,
{
n
_
,
l
i
s
t
_
}
]
:
=
{
z
,
M
a
p
A
t
[
(
#
+
1
)
&
,
l
i
s
t
,
r
]
}
c
m
E
x
e
c
u
t
e
[
i
n
c
[
r
_
]
,
{
n
_
,
l
i
s
t
_
}
]
:
=
c
m
E
x
e
c
u
t
e
[
i
n
c
[
r
,
(
n
+
1
)
]
,
{
n
,
l
i
s
t
}
]
c
m
E
x
e
c
u
t
e
[
d
e
c
[
r
_
,
z
_
]
,
{
n
_
,
l
i
s
t
_
}
]
:
=
I
f
[
l
i
s
t
[
[
r
]
]
≤
0
,
{
n
+
1
,
l
i
s
t
}
,
{
z
,
M
a
p
A
t
[
(
#
-
1
)
&
,
l
i
s
t
,
r
]
}
]
c
m
E
x
e
c
u
t
e
[
d
e
c
[
r
_
]
,
{
n
_
,
l
i
s
t
_
}
]
:
=
c
m
E
x
e
c
u
t
e
[
d
e
c
[
r
,
(
n
+
1
)
]
,
{
n
,
l
i
s
t
}
]
c
m
E
x
e
c
u
t
e
[
c
l
r
[
r
_
]
,
{
n
_
,
l
i
s
t
_
}
]
:
=
{
n
+
1
,
M
a
p
A
t
[
0
&
,
l
i
s
t
,
r
]
}
c
m
E
x
e
c
u
t
e
[
c
p
y
[
r
1
_
,
r
2
_
]
,
{
n
_
,
l
i
s
t
_
}
]
:
=
{
n
+
1
,
M
a
p
A
t
[
l
i
s
t
[
[
r
1
]
]
&
,
l
i
s
t
,
r
2
]
}
c
m
E
x
e
c
u
t
e
[
j
[
z
_
]
,
{
n
_
,
l
i
s
t
_
}
]
:
=
{
z
,
l
i
s
t
}
c
m
E
x
e
c
u
t
e
[
j
z
[
r
_
,
z
T
r
u
e
_
,
z
F
a
l
s
e
_
]
,
{
n
_
,
l
i
s
t
_
}
]
:
=
I
f
[
l
i
s
t
[
[
r
]
]
0
,
{
z
T
r
u
e
,
l
i
s
t
}
,
{
z
F
a
l
s
e
,
l
i
s
t
}
]
c
m
E
x
e
c
u
t
e
[
j
n
z
[
r
_
,
z
T
r
u
e
_
,
z
F
a
l
s
e
_
]
,
{
n
_
,
l
i
s
t
_
}
]
:
=
I
f
[
l
i
s
t
[
[
r
]
]
≠
0
,
{
z
T
r
u
e
,
l
i
s
t
}
,
{
z
F
a
l
s
e
,
l
i
s
t
}
]
c
m
E
x
e
c
u
t
e
[
j
z
d
e
c
[
r
_
,
z
T
r
u
e
_
,
z
F
a
l
s
e
_
]
,
{
n
_
,
l
i
s
t
_
}
]
:
=
I
f
[
l
i
s
t
[
[
r
]
]
0
,
{
z
T
r
u
e
,
l
i
s
t
}
,
c
m
E
x
e
c
u
t
e
[
d
e
c
[
r
,
z
F
a
l
s
e
]
,
{
n
,
l
i
s
t
}
]
]
c
m
E
x
e
c
u
t
e
[
j
e
[
r
1
_
,
r
2
_
,
z
T
r
u
e
_
,
z
F
a
l
s
e
_
]
,
{
n
_
,
l
i
s
t
_
}
]
:
=
I
f
[
l
i
s
t
[
[
r
1
]
]
l
i
s
t
[
[
r
2
]
]
,
{
z
T
r
u
e
,
l
i
s
t
}
,
{
z
F
a
l
s
e
,
l
i
s
t
}
]
The function above, when tested on a random counter machine, works perfectly.
Run a two-register counter machine with 5 instructions for 10 steps:
I
n
[
]
:
=
c
m
=
c
o
u
n
t
e
r
M
a
c
h
i
n
e
[
2
]
;
i
n
s
t
r
u
c
t
i
o
n
s
=
{
i
n
c
[
1
]
,
d
e
c
[
2
,
1
]
,
i
n
c
[
2
]
,
d
e
c
[
1
,
3
]
,
d
e
c
[
2
,
1
]
}
;
c
m
E
v
o
l
v
e
L
i
s
t
[
i
n
s
t
r
u
c
t
i
o
n
s
,
c
m
,
1
0
]
O
u
t
[
]
=
{
{
1
,
{
0
,
0
}
}
,
{
2
,
{
1
,
0
}
}
,
{
3
,
{
1
,
0
}
}
,
{
4
,
{
1
,
1
}
}
,
{
3
,
{
0
,
1
}
}
,
{
4
,
{
0
,
2
}
}
,
{
5
,
{
0
,
2
}
}
,
{
1
,
{
0
,
1
}
}
,
{
2
,
{
1
,
1
}
}
,
{
1
,
{
1
,
0
}
}
,
{
2
,
{
2
,
0
}
}
}
Types of Counter Machines
I
n
[
]
:
=
Counter Machine Instruction Sets
There are 5 main types of counter machines, characterized by their instruction sets. Essentially, each type of counter machine has a specific set of instructions in a specific order. These 5 types are the Shepherdson-Sturgis machine, the Minsky machine (aka the Abacus machine/Lambek machine), the Program machine/Program computer, the Successor machine, and the Elgot-Robinson model. Each counter machine's instruction is shown below.
Note: The variables used in the machine instruction set are arbitrary; the instructions in the set and the order of the instructions is what matters.
Show the instruction set for a Shepherdson-Sturgis machine:
I
n
[
]
:
=
{
I
N
C
[
r
]
,
D
E
C
[
r
]
,
C
L
R
[
r
]
,
C
P
Y
[
r
1
,
r
2
]
,
J
N
Z
[
r
,
z
]
,
J
[
z
]
}
;
Show the instruction set for a Minsky machine (aka Abacus machine/Lambek machine):
I
n
[
]
:
=
{
I
N
C
[
r
,
z
]
,
J
Z
D
E
C
[
r
,
z
T
r
u
e
,
z
F
a
l
s
e
]
}
;
Show the instruction set for a Program machine/Program computer:
I
n
[
]
:
=
{
I
N
C
[
r
]
,
D
E
C
[
r
]
,
J
Z
[
r
,
r
T
r
u
e
]
}
;
Show the instruction set for a Successor machine:
I
n
[
]
:
=
{
C
L
R
[
r
]
,
I
N
C
[
r
]
,
J
E
[
r
1
,
r
2
,
z
]
}
;
Show the instruction set for an Elgot-Robinson model:
I
n
[
]
:
=
{
I
N
C
[
r
]
,
C
P
Y
[
r
1
,
r
2
]
,
J
E
[
r
1
,
r
1
,
z
]
}
;
I
n
[
]
:
=
Modeling Counter Machines
Using the counter machine and the instruction set created above, the different counter machines can be evaluated for any number of steps. The counter machine is expressed with
Grid
and
ArrayPlot
, displayed side-by-side with
GraphicsRow
. For the grid, the left side shows the current instruction and the right side shows the registers. For the ArrayPlot, the leftmost column is the instruction, the middle column shows the value of register 1, and the right column shows the value of register 2.
Note: For the ArrayPlot, the colors get darker as the number increases. If two colors are the same, they have the same value.
Shepherdson-Sturgis Machine
Model the evolution of a Shepherdson-Sturgis machine for 15 steps:
I
n
[
]
:
=
M
o
d
u
l
e
[
{
s
s
M
a
c
h
i
n
e
=
c
o
u
n
t
e
r
M
a
c
h
i
n
e
[
2
]
,
s
s
M
a
c
h
i
n
e
I
n
s
t
r
u
c
t
i
o
n
s
=
{
i
n
c
[
1
]
,
d
e
c
[
2
]
,
c
l
r
[
1
]
,
c
p
y
[
2
,
1
]
,
j
n
z
[
2
,
3
,
6
]
,
j
[
1
]
}
,
s
s
M
a
c
h
i
n
e
T
a
b
l
e
}
,
s
s
M
a
c
h
i
n
e
T
a
b
l
e
=
c
m
E
v
o
l
v
e
L
i
s
t
[
s
s
M
a
c
h
i
n
e
I
n
s
t
r
u
c
t
i
o
n
s
,
s
s
M
a
c
h
i
n
e
,
1
5
]
;
G
r
a
p
h
i
c
s
R
o
w
[
{
S
t
y
l
e
[
G
r
i
d
[
s
s
M
a
c
h
i
n
e
T
a
b
l
e
,
F
r
a
m
e
A
l
l
]
,
R
G
B
C
o
l
o
r
[
0
.
8
,
0
.
3
6
,
0
.
4
1
]
,
1
7
]
,
A
r
r
a
y
P
l
o
t
[
P
a
r
t
i
t
i
o
n
[
F
l
a
t
t
e
n
[
s
s
M
a
c
h
i
n
e
T
a
b
l
e
]
,
3
]
,
M
e
s
h
T
r
u
e
]
}
]
]
O
u
t
[
]
=
Minsky Machine (aka Abacus Machine/Lambek Machine)
Model the evolution of a Minsky machine for 15 steps:
I
n
[
]
:
=
M
o
d
u
l
e
[
{
m
i
n
s
k
y
M
a
c
h
i
n
e
=
c
o
u
n
t
e
r
M
a
c
h
i
n
e
[
2
]
,
m
i
n
s
k
y
M
a
c
h
i
n
e
I
n
s
t
r
u
c
t
i
o
n
s
=
{
i
n
c
[
1
,
2
]
,
j
z
d
e
c
[
2
,
1
,
2
]
}
,
m
i
n
s
k
y
M
a
c
h
i
n
e
T
a
b
l
e
}
,
m
i
n
s
k
y
M
a
c
h
i
n
e
T
a
b
l
e
=
c
m
E
v
o
l
v
e
L
i
s
t
[
m
i
n
s
k
y
M
a
c
h
i
n
e
I
n
s
t
r
u
c
t
i
o
n
s
,
m
i
n
s
k
y
M
a
c
h
i
n
e
,
1
5
]
;
G
r
a
p
h
i
c
s
R
o
w
[
{
S
t
y
l
e
[
G
r
i
d
[
m
i
n
s
k
y
M
a
c
h
i
n
e
T
a
b
l
e
,
F
r
a
m
e
A
l
l
]
,
R
G
B
C
o
l
o
r
[
0
.
8
,
0
.
3
6
,
0
.
4
1
]
,
1
7
]
,
A
r
r
a
y
P
l
o
t
[
P
a
r
t
i
t
i
o
n
[
F
l
a
t
t
e
n
[
m
i
n
s
k
y
M
a
c
h
i
n
e
T
a
b
l
e
]
,
3
]
,
M
e
s
h
T
r
u
e
]
}
]
]
O
u
t
[
]
=
Program Machine/Program Computer
Model the evolution of a Program machine for 15 steps:
I
n
[
]
:
=
M
o
d
u
l
e
[
{
p
M
a
c
h
i
n
e
=
c
o
u
n
t
e
r
M
a
c
h
i
n
e
[
2
]
,
p
M
a
c
h
i
n
e
I
n
s
t
r
u
c
t
i
o
n
s
=
{
i
n
c
[
2
]
,
d
e
c
[
1
]
,
j
z
[
2
,
2
,
1
]
}
,
p
M
a
c
h
i
n
e
T
a
b
l
e
}
,
p
M
a
c
h
i
n
e
T
a
b
l
e
=
c
m
E
v
o
l
v
e
L
i
s
t
[
p
M
a
c
h
i
n
e
I
n
s
t
r
u
c
t
i
o
n
s
,
p
M
a
c
h
i
n
e
,
1
5
]
;
G
r
a
p
h
i
c
s
R
o
w
[
{
S
t
y
l
e
[
G
r
i
d
[
p
M
a
c
h
i
n
e
T
a
b
l
e
,
F
r
a
m
e
A
l
l
]
,
R
G
B
C
o
l
o
r
[
0
.
8
,
0
.
3
6
,
0
.
4
1
]
,
1
7
]
,
A
r
r
a
y
P
l
o
t
[
P
a
r
t
i
t
i
o
n
[
F
l
a
t
t
e
n
[
p
M
a
c
h
i
n
e
T
a
b
l
e
]
,
3
]
,
M
e
s
h
T
r
u
e
]
}
]
]
O
u
t
[
]
=
Successor Machine
Model the evolution of a Successor machine for 15 steps:
I
n
[
]
:
=
M
o
d
u
l
e
[
{
s
u
c
c
M
a
c
h
i
n
e
=
c
o
u
n
t
e
r
M
a
c
h
i
n
e
[
2
]
,
s
u
c
c
M
a
c
h
i
n
e
I
n
s
t
r
u
c
t
i
o
n
s
=
{
c
l
r
[
2
]
,
i
n
c
[
2
]
,
j
e
[
2
,
1
,
2
,
1
]
}
,
s
u
c
c
M
a
c
h
i
n
e
T
a
b
l
e
}
,
s
u
c
c
M
a
c
h
i
n
e
T
a
b
l
e
=
c
m
E
v
o
l
v
e
L
i
s
t
[
s
u
c
c
M
a
c
h
i
n
e
I
n
s
t
r
u
c
t
i
o
n
s
,
s
u
c
c
M
a
c
h
i
n
e
,
1
5
]
;
G
r
a
p
h
i
c
s
R
o
w
[
{
S
t
y
l
e
[
G
r
i
d
[
s
u
c
c
M
a
c
h
i
n
e
T
a
b
l
e
,
F
r
a
m
e
A
l
l
]
,
R
G
B
C
o
l
o
r
[
0
.
8
,
0
.
3
6
,
0
.
4
1
]
,
1
7
]
,
A
r
r
a
y
P
l
o
t
[
P
a
r
t
i
t
i
o
n
[
F
l
a
t
t
e
n
[
s
u
c
c
M
a
c
h
i
n
e
T
a
b
l
e
]
,
3
]
,
M
e
s
h
T
r
u
e
]
}
]
]
O
u
t
[
]
=
Elgot-Robinson Model
Model the evolution of an Elgot-Robinson model for 15 steps:
I
n
[
]
:
=
M
o
d
u
l
e
[
{
e
r
M
a
c
h
i
n
e
=
c
o
u
n
t
e
r
M
a
c
h
i
n
e
[
2
]
,
e
r
M
a
c
h
i
n
e
I
n
s
t
r
u
c
t
i
o
n
s
=
{
i
n
c
[
1
]
,
c
p
y
[
1
,
2
]
,
j
e
[
1
,
2
,
1
,
1
]
}
,
e
r
M
a
c
h
i
n
e
T
a
b
l
e
}
,
e
r
M
a
c
h
i
n
e
T
a
b
l
e
=
c
m
E
v
o
l
v
e
L
i
s
t
[
e
r
M
a
c
h
i
n
e
I
n
s
t
r
u
c
t
i
o
n
s
,
e
r
M
a
c
h
i
n
e
,
1
5
]
;
G
r
a
p
h
i
c
s
R
o
w
[
{
S
t
y
l
e
[
G
r
i
d
[
e
r
M
a
c
h
i
n
e
T
a
b
l
e
,
F
r
a
m
e
A
l
l
]
,
R
G
B
C
o
l
o
r
[
0
.
8
,
0
.
3
6
,
0
.
4
1
]
,
1
7
]
,
A
r
r
a
y
P
l
o
t
[
P
a
r
t
i
t
i
o
n
[
F
l
a
t
t
e
n
[
e
r
M
a
c
h
i
n
e
T
a
b
l
e
]
,
3
]
,
M
e
s
h
T
r
u
e
]
}
]
]
O
u
t
[
]
=
Establishing Unpredictability
Predictability Functions
Armed with a counter machine function, the final goal of this project is to find which counter machine, of the types stated above, is the most unpredictable. To find the most unpredictable counter machine, the first step is to create functions that determine predictability.
One necessary function is one that checks for repeating register values over many iterations of the counter machine. The built-in function
FindTransientRepeat
finds repeats with a transient in a list (a transient is a beginning "phrase" of values that aren't included in the repeats). To create a function that finds repeating register values, the function FindTransientRepeat is applied to a list of register values; if FIndTransientRepeat returns an empty list, there is no repeat.
Check for repeating register values:
I
n
[
]
:
=
c
h
e
c
k
R
e
p
e
a
t
[
c
m
_
L
i
s
t
]
:
=
L
e
n
g
t
h
[
F
i
n
d
T
r
a
n
s
i
e
n
t
R
e
p
e
a
t
[
c
m
[
[
A
l
l
,
2
]
]
,
4
]
[
[
2
]
]
]
0
Another necessary function is one that searches for a pattern in the register values. The function
FindSequenceFunction
is the best option in this situation. FindSequenceFunction finds a function that can express a list of values. If the register values appear in a pattern, the FindSequenceFunction will most likely find it.
To create a function that checks for a pattern in the register values, FindSequenceFunction is applied to the register values from the counter machine function. If FindSequenceFunction can’t find a way to express the input list, it’ll return an expression with the head FindSequenceFunction, which means the counter machine doesn’t have a pattern.
Search for a pattern in register values:
I
n
[
]
:
=
c
h
e
c
k
P
a
t
t
e
r
n
[
c
m
_
L
i
s
t
]
:
=
H
e
a
d
[
F
i
n
d
S
e
q
u
e
n
c
e
F
u
n
c
t
i
o
n
[
F
l
a
t
t
e
n
[
c
m
[
[
A
l
l
,
2
]
]
]
,
T
i
m
e
C
o
n
s
t
r
a
i
n
t
3
]
]
=
=
=
F
i
n
d
S
e
q
u
e
n
c
e
F
u
n
c
t
i
o
n
Using these two functions, a general predictability function can be written. Essentially, when given counter machine values, it checks if
checkrepeat
and
checkpattern
can find repeating values or a pattern; if neither function can, then the counter machine input is unpredictable.
Use
checkRepeat
and
checkPattern
to create a predictability function:
I
n
[
]
:
=
p
r
e
d
i
c
t
a
b
i
l
i
t
y
T
e
s
t
[
c
m
_
L
i
s
t
]
:
=
I
f
[
c
h
e
c
k
R
e
p
e
a
t
[
c
m
]
&
&
c
h
e
c
k
P
a
t
t
e
r
n
[
c
m
]
,
"
U
n
p
r
e
d
i
c
t
a
b
l
e
"
,
"
P
r
e
d
i
c
t
a
b
l
e
"
]
Below, the
predictabilityTest
function is tested with the 5 examples of counter machine instructions used above. In these tests, the counter machine function executes for 30 steps.
Shepherdson-Sturgis Machine
Run
predictabilityTest
on a random Shepherdson-Sturgis machine:
I
n
[
]
:
=
s
s
P
r
e
d
i
c
t
a
b
i
l
i
t
y
T
e
s
t
=
c
m
E
v
o
l
v
e
L
i
s
t
[
{
i
n
c
[
1
]
,
d
e
c
[
2
]
,
c
l
r
[
1
]
,
c
p
y
[
2
,
1
]
,
j
n
z
[
2
,
3
,
6
]
,
j
[
1
]
}
,
c
o
u
n
t
e
r
M
a
c
h
i
n
e
[
2
]
,
3
0
]
;
p
r
e
d
i
c
t
a
b
i
l
i
t
y
T
e
s
t
[
s
s
P
r
e
d
i
c
t
a
b
i
l
i
t
y
T
e
s
t
]
O
u
t
[
]
=
P
r
e
d
i
c
t
a
b
l
e
Minsky Machine (aka Abacus Machine/Lambek Machine)
Run
predictabilityTest
on a random Minsky machine:
I
n
[
]
:
=
m
i
n
s
k
y
P
r
e
d
i
c
t
a
b
i
l
i
t
y
T
e
s
t
=
c
m
E
v
o
l
v
e
L
i
s
t
[
{
i
n
c
[
1
,
2
]
,
j
z
d
e
c
[
2
,
1
,
2
]
}
,
c
o
u
n
t
e
r
M
a
c
h
i
n
e
[
2
]
,
3
0
]
;
p
r
e
d
i
c
t
a
b
i
l
i
t
y
T
e
s
t
[
m
i
n
s
k
y
P
r
e
d
i
c
t
a
b
i
l
i
t
y
T
e
s
t
]
O
u
t
[
]
=
P
r
e
d
i
c
t
a
b
l
e
Program Machine/Program Computer
Run
predictabilityTest
on a random Program machine:
I
n
[
]
:
=
p
r
o
g
r
a
m
P
r
e
d
i
c
t
a
b
i
l
i
t
y
T
e
s
t
=
c
m
E
v
o
l
v
e
L
i
s
t
[
{
i
n
c
[
2
]
,
d
e
c
[
1
]
,
j
z
[
2
,
2
,
1
]
}
,
c
o
u
n
t
e
r
M
a
c
h
i
n
e
[
2
]
,
3
0
]
;
p
r
e
d
i
c
t
a
b
i
l
i
t
y
T
e
s
t
[
p
r
o
g
r
a
m
P
r
e
d
i
c
t
a
b
i
l
i
t
y
T
e
s
t
]
O
u
t
[
]
=
P
r
e
d
i
c
t
a
b
l
e
Successor Machine
Run
predictabilityTest
on a random Successor machine:
I
n
[
]
:
=
s
u
c
c
P
r
e
d
i
c
t
a
b
i
l
i
t
y
T
e
s
t
=
c
m
E
v
o
l
v
e
L
i
s
t
[
{
c
l
r
[
2
]
,
i
n
c
[
2
]
,
j
e
[
2
,
1
,
2
,
1
]
}
,
c
o
u
n
t
e
r
M
a
c
h
i
n
e
[
2
]
,
3
0
]
;
p
r
e
d
i
c
t
a
b
i
l
i
t
y
T
e
s
t
[
s
u
c
c
P
r
e
d
i
c
t
a
b
i
l
i
t
y
T
e
s
t
]
O
u
t
[
]
=
P
r
e
d
i
c
t
a
b
l
e
Elgot-Robinson Model
Run
predictabilityTest
on a random Elgot-Robinson model:
I
n
[
]
:
=
e
r
P
r
e
d
i
c
t
a
b
i
l
i
t
y
T
e
s
t
=
c
m
E
v
o
l
v
e
L
i
s
t
[
{
i
n
c
[
1
]
,
c
p
y
[
1
,
2
]
,
j
e
[
1
,
2
,
1
,
1
]
}
,
c
o
u
n
t
e
r
M
a
c
h
i
n
e
[
2
]
,
3
0
]
;
p
r
e
d
i
c
t
a
b
i
l
i
t
y
T
e
s
t
[
e
r
P
r
e
d
i
c
t
a
b
i
l
i
t
y
T
e
s
t
]
O
u
t
[
]
=
P
r
e
d
i
c
t
a
b
l
e
As expected, the function determined that all 5 counter machine examples tested were predictable.
Unpredictable Counter Machines
The
predictabilityTest
function can now be used on the 5 types of counter machines in order to find ones that are not predictable. For each type of counter machine, the
predictabilityTest
function will be applied to every possible permutation of values for the corresponding instruction set. Using the function Table to iterate over the possible values for each variable creates a list of possible permutations. After finding counter machines that aren't predictable, they can be analyzed to determine whether or not they're truly unpredictable.
Note: The computations run below can take some time to run, due to the volume of possibilities.
◼
Shepherdson-Sturgis Machine: 13824 possibilities
◼
Minsky Machine: 32 possibilities
◼
Program Machine: 72 possibilities
◼
Successor Machine: 144 possibilities
◼
Elgot-Robinson Model: 288 possibilities
Find the Shepherdson-Sturgis machine instruction sets that create unpredictable counter machines:
a
l
P
o
s
s
i
b
l
e
S
S
M
a
c
h
i
n
e
s
=
F
l
a
t
t
e
n
[
T
a
b
l
e
[
{
i
n
c
[
r
1
]
,
d
e
c
[
r
2
]
,
c
l
r
[
r
3
]
,
c
p
y
[
r
4
,
r
5
]
,
j
n
z
[
r
6
,
z
1
,
z
2
]
,
j
[
z
3
]
}
,
{
r
1
,
2
}
,
{
r
2
,
2
}
,
{
r
3
,
2
}
,
{
r
4
,
2
}
,
{
r
5
,
2
}
,
{
r
6
,
2
}
,
{
z
1
,
6
}
,
{
z
2
,
6
}
,
{
z
3
,
6
}
]
,
8
]
;
p
r
e
d
i
c
t
a
b
i
l
i
t
y
S
S
=
I
f
[
p
r
e
d
i
c
t
a
b
i
l
i
t
y
T
e
s
t
[
c
m
E
v
o
l
v
e
L
i
s
t
[
#
,
c
o
u
n
t
e
r
M
a
c
h
i
n
e
[
2
]
,
3
0
]
]
"
U
n
p
r
e
d
i
c
t
a
b
l
e
"
,
#
,
N
o
t
h
i
n
g
]
&
/
@
a
l
P
o
s
s
i
b
l
e
S
S
M
a
c
h
i
n
e
s
O
u
t
[
]
=
{
{
i
n
c
[
1
]
,
d
e
c
[
2
]
,
c
l
r
[
2
]
,
c
p
y
[
1
,
2
]
,
j
n
z
[
1
,
1
,
1
]
,
j
[
6
]
}
,
{
i
n
c
[
1
]
,
d
e
c
[
2
]
,
c
l
r
[
2
]
,
c
p
y
[
1
,
2
]
,
j
n
z
[
1
,
1
,
4
]
,
j
[
3
]
}
,
{
i
n
c
[
1
]
,
d
e
c
[
2
]
,
c
l
r
[
2
]
,
c
p
y
[
1
,
2
]
,
j
n
z
[
1
,
1
,
5
]
,
j
[
1
]
}
,
{
i
n
c
[
1
]
,
d
e
c
[
2
]
,
c
l
r
[
2
]
,
c
p
y
[
1
,
2
]
,
j
n
z
[
1
,
1
,
5
]
,
j
[
2
]
}
,
{
i
n
c
[
1
]
,
d
e
c
[
2
]
,
c
l
r
[
2
]
,
c
p
y
[
1
,
2
]
,
j
n
z
[
1
,
1
,
5
]
,
j
[
3
]
}
,
{
i
n
c
[
1
]
,
d
e
c
[
2
]
,
c
l
r
[
2
]
,
c
p
y
[
1
,
2
]
,
j
n
z
[
1
,
1
,
6
]
,
j
[
1
]
}
,
{
i
n
c
[
1
]
,
d
e
c
[
2
]
,
c
l
r
[
2
]
,
c
p
y
[
1
,
2
]
,
j
n
z
[
1
,
1
,
6
]
,
j
[
2
]
}
,
{
i
n
c
[
1
]
,
d
e
c
[
2
]
,
c
l
r
[
2
]
,
c
p
y
[
1
,
2
]
,
j
n
z
[
1
,
1
,
6
]
,
j
[
5
]
}
,
{
i
n
c
[
1
]
,
d
e
c
[
2
]
,
c
l
r
[
2
]
,
c
p
y
[
1
,
2
]
,
j
n
z
[
1
,
1
,
6
]
,
j
[
6
]
}
,
{
i
n
c
[
1
]
,
d
e
c
[
2
]
,
c
l
r
[
2
]
,
c
p
y
[
1
,
2
]
,
j
n
z
[
1
,
6
,
1
]
,
j
[
1
]
}
,
{
i
n
c
[
1
]
,
d
e
c
[
2
]
,
c
l
r
[
2
]
,
c
p
y
[
1
,
2
]
,
j
n
z
[
1
,
6
,
2
]
,
j
[
1
]
}
,
{
i
n
c
[
1
]
,
d
e
c
[
2
]
,
c
l
r
[
2
]
,
c
p
y
[
1
,
2
]
,
j
n
z
[
1
,
6
,
3
]
,
j
[
1
]
}
,
{
i
n
c
[
1
]
,
d
e
c
[
2
]
,
c
l
r
[
2
]
,
c
p
y
[
1
,
2
]
,
j
n
z
[
1
,
6
,
4
]
,
j
[
1
]
}
,
{
i
n
c
[
2
]
,
d
e
c
[
1
]
,
c
l
r
[
1
]
,
c
p
y
[
2
,
1
]
,
j
n
z
[
2
,
1
,
3
]
,
j
[
4
]
}
,
{
i
n
c
[
2
]
,
d
e
c
[
1
]
,
c
l
r
[
1
]
,
c
p
y
[
2
,
1
]
,
j
n
z
[
2
,
1
,
3
]
,
j
[
6
]
}
,
{
i
n
c
[
2
]
,
d
e
c
[
1
]
,
c
l
r
[
1
]
,
c
p
y
[
2
,
1
]
,
j
n
z
[
2
,
1
,
6
]
,
j
[
6
]
}
,
{
i
n
c
[
2
]
,
d
e
c
[
1
]
,
c
l
r
[
1
]
,
c
p
y
[
2
,
1
]
,
j
n
z
[
2
,
6
,
1
]
,
j
[
1
]
}
,
{
i
n
c
[
2
]
,
d
e
c
[
1
]
,
c
l
r
[
1
]
,
c
p
y
[
2
,
1
]
,
j
n
z
[
2
,
6
,
2
]
,
j
[
1
]
}
,
{
i
n
c
[
2
]
,
d
e
c
[
1
]
,
c
l
r
[
1
]
,
c
p
y
[
2
,
1
]
,
j
n
z
[
2
,
6
,
3
]
,
j
[
1
]
}
,
{
i
n
c
[
2
]
,
d
e
c
[
1
]
,
c
l
r
[
1
]
,
c
p
y
[
2
,
1
]
,
j
n
z
[
2
,
6
,
4
]
,
j
[
1
]
}
,
{
i
n
c
[
2
]
,
d
e
c
[
1
]
,
c
l
r
[
1
]
,
c
p
y
[
2
,
1
]
,
j
n
z
[
2
,
6
,
5
]
,
j
[
1
]
}
,
{
i
n
c
[
2
]
,
d
e
c
[
1
]
,
c
l
r
[
1
]
,
c
p
y
[
2
,
1
]
,
j
n
z
[
2
,
6
,
6
]
,
j
[
1
]
}
}
Find the Minsky machine instruction sets that create unpredictable counter machines:
a
l
l
P
o
s
s
i
b
l
e
M
i
n
s
k
y
M
a
c
h
i
n
e
s
=
F
l
a
t
t
e
n
[
T
a
b
l
e
[
{
i
n
c
[
r
1
,
z
1
]
,
j
z
d
e
c
[
r
2
,
z
2
,
z
3
]
}
,
{
r
1
,
2
}
,
{
r
2
,
2
}
,
{
z
1
,
2
}
,
{
z
2
,
2
}
,
{
z
3
,
2
}
]
,
4
]
;
p
r
e
d
i
c
t
a
b
i
l
i
t
y
M
i
n
s
k
y
=
I
f
[
p
r
e
d
i
c
t
a
b
i
l
i
t
y
T
e
s
t
[
c
m
E
v
o
l
v
e
L
i
s
t
[
#
,
c
o
u
n
t
e
r
M
a
c
h
i
n
e
[
2
]
,
3
0
]
]
"
U
n
p
r
e
d
i
c
t
a
b
l
e
"
,
#
,
N
o
t
h
i
n
g
]
&
/
@
a
l
l
P
o
s
s
i
b
l
e
M
i
n
s
k
y
M
a
c
h
i
n
e
s
O
u
t
[
]
=
{
}
Find the Program machine instruction sets that create unpredictable counter machines:
a
l
l
p
o
s
s
i
b
l
e
P
M
a
c
h
i
n
e
s
=
F
l
a
t
t
e
n
[
T
a
b
l
e
[
{
i
n
c
[
r
1
]
,
d
e
c
[
r
2
]
,
j
z
[
r
3
,
z
1
,
z
2
]
}
,
{
r
1
,
2
}
,
{
r
2
,
2
}
,
{
r
3
,
2
}
,
{
z
1
,
3
}
,
{
z
2
,
3
}
]
,
4
]
;
p
r
e
d
i
c
t
a
b
i
l
i
t
y
P
r
o
g
r
a
m
=
I
f
[
p
r
e
d
i
c
t
a
b
i
l
i
t
y
T
e
s
t
[
c
m
E
v
o
l
v
e
L
i
s
t
[
#
,
c
o
u
n
t
e
r
M
a
c
h
i
n
e
[
2
]
,
3
0
]
]
"
U
n
p
r
e
d
i
c
t
a
b
l
e
"
,
#
,
N
o
t
h
i
n
g
]
&
/
@
a
l
l
p
o
s
s
i
b
l
e
P
M
a
c
h
i
n
e
s
O
u
t
[
]
=
{
}
Find the Successor machine instruction sets that create unpredictable counter machines:
a
l
l
P
o
s
s
i
b
l
e
S
u
c
c
M
a
c
h
i
n
e
s
=
F
l
a
t
t
e
n
[
T
a
b
l
e
[
{
c
l
r
[
r
1
]
,
i
n
c
[
r
2
]
,
j
e
[
r
3
,
r
4
,
z
1
,
z
2
]
}
,
{
r
1
,
2
}
,
{
r
2
,
2
}
,
{
r
3
,
2
}
,
{
r
4
,
2
}
,
{
z
1
,
3
}
,
{
z
2
,
3
}
]
,
5
]
;
p
r
e
d
i
c
t
a
b
i
l
i
t
y
S
U
C
C
=
I
f
[
p
r
e
d
i
c
t
a
b
i
l
i
t
y
T
e
s
t
[
c
m
E
v
o
l
v
e
L
i
s
t
[
#
,
c
o
u
n
t
e
r
M
a
c
h
i
n
e
[
2
]
,
3
0
]
]
"
U
n
p
r
e
d
i
c
t
a
b
l
e
"
,
#
,
N
o
t
h
i
n
g
]
&
/
@
a
l
l
P
o
s
s
i
b
l
e
S
u
c
c
M
a
c
h
i
n
e
s
O
u
t
[
]
=
{
}
Find the Elgot-Robinson model instruction sets that create unpredictable counter machines:
a
l
l
P
o
s
s
i
b
l
e
E
r
M
a
c
h
i
n
e
s
=
F
l
a
t
t
e
n
[
T
a
b
l
e
[
{
i
n
c
[
r
1
]
,
c
p
y
[
r
2
,
r
3
]
,
j
e
[
r
4
,
r
5
,
z
1
,
z
2
]
}
,
{
r
1
,
2
}
,
{
r
2
,
2
}
,
{
r
3
,
2
}
,
{
r
4
,
2
}
,
{
r
5
,
2
}
,
{
z
1
,
3
}
,
{
z
2
,
3
}
]
,
6
]
;
p
r
e
d
i
c
t
a
b
i
l
i
t
y
E
R
=
I
f
[
p
r
e
d
i
c
t
a
b
i
l
i
t
y
T
e
s
t
[
c
m
E
v
o
l
v
e
L
i
s
t
[
#
,
c
o
u
n
t
e
r
M
a
c
h
i
n
e
[
2
]
,
3
0
]
]
"
U
n
p
r
e
d
i
c
t
a
b
l
e
"
,
#
,
N
o
t
h
i
n
g
]
&
/
@
a
l
l
P
o
s
s
i
b
l
e
E
r
M
a
c
h
i
n
e
s
O
u
t
[
]
=
{
}
Tests for the Minsky machine, the Program machine, the Successor machine, and the Elgot-Robinson model didn't return any instruction sets marked unpredictable. However, the Shepherdson-Sturgis machine tests returned 22 possible unpredictable instruction sets. With this list, the first step is to eliminate any instruction sets that return duplicate counter machines.
Delete duplicate counter machines from the list of instruction sets:
I
n
[
]
:
=
p
r
e
d
i
c
t
a
b
i
l
i
t
y
S
S
=
L
i
s
t
I
c
o
n
;
s
s
P
o
s
s
i
b
i
l
i
t
i
e
s
=
D
e
l
e
t
e
D
u
p
l
i
c
a
t
e
s
[
c
m
E
v
o
l
v
e
L
i
s
t
[
#
,
c
o
u
n
t
e
r
M
a
c
h
i
n
e
[
2
]
,
1
5
]
&
/
@
p
r
e
d
i
c
t
a
b
i
l
i
t
y
S
S
]
O
u
t
[
]
=
{
{
{
1
,
{
0
,
0
}
}
,
{
2
,
{
1
,
0
}
}
,
{
3
,
{
1
,
0
}
}
,
{
4
,
{
1
,
0
}
}
,
{
5
,
{
1
,
1
}
}
,
{
1
,
{
1
,
1
}
}
,
{
2
,
{
2
,
1
}
}
,
{
3
,
{
2
,
0
}
}
,
{
4
,
{
2
,
0
}
}
,
{
5
,
{
2
,
2
}
}
,
{
1
,
{
2
,
2
}
}
,
{
2
,
{
3
,
2
}
}
,
{
3
,
{
3
,
1
}
}
,
{
4
,
{
3
,
0
}
}
,
{
5
,
{
3
,
3
}
}
,
{
1
,
{
3
,
3
}
}
}
,
{
{
1
,
{
0
,
0
}
}
,
{
2
,
{
1
,
0
}
}
,
{
3
,
{
1
,
0
}
}
,
{
4
,
{
1
,
0
}
}
,
{
5
,
{
1
,
1
}
}
,
{
6
,
{
1
,
1
}
}
,
{
1
,
{
1
,
1
}
}
,
{
2
,
{
2
,
1
}
}
,
{
3
,
{
2
,
0
}
}
,
{
4
,
{
2
,
0
}
}
,
{
5
,
{
2
,
2
}
}
,
{
6
,
{
2
,
2
}
}
,
{
1
,
{
2
,
2
}
}
,
{
2
,
{
3
,
2
}
}
,
{
3
,
{
3
,
1
}
}
,
{
4
,
{
3
,
0
}
}
}
,
{
{
1
,
{
0
,
0
}
}
,
{
2
,
{
0
,
1
}
}
,
{
3
,
{
0
,
1
}
}
,
{
4
,
{
0
,
1
}
}
,
{
5
,
{
1
,
1
}
}
,
{
1
,
{
1
,
1
}
}
,
{
2
,
{
1
,
2
}
}
,
{
3
,
{
0
,
2
}
}
,
{
4
,
{
0
,
2
}
}
,
{
5
,
{
2
,
2
}
}
,
{
1
,
{
2
,
2
}
}
,
{
2
,
{
2
,
3
}
}
,
{
3
,
{
1
,
3
}
}
,
{
4
,
{
0
,
3
}
}
,
{
5
,
{
3
,
3
}
}
,
{
1
,
{
3
,
3
}
}
}
,
{
{
1
,
{
0
,
0
}
}
,
{
2
,
{
0
,
1
}
}
,
{
3
,
{
0
,
1
}
}
,
{
4
,
{
0
,
1
}
}
,
{
5
,
{
1
,
1
}
}
,
{
6
,
{
1
,
1
}
}
,
{
1
,
{
1
,
1
}
}
,
{
2
,
{
1
,
2
}
}
,
{
3
,
{
0
,
2
}
}
,
{
4
,
{
0
,
2
}
}
,
{
5
,
{
2
,
2
}
}
,
{
6
,
{
2
,
2
}
}
,
{
1
,
{
2
,
2
}
}
,
{
2
,
{
2
,
3
}
}
,
{
3
,
{
1
,
3
}
}
,
{
4
,
{
0
,
3
}
}
}
}
Visualizing these counter machines would make it easier to understand whether or not these counter machines are truly unpredictable.
Use Grid and ArrayPlot to model the counter machines:
I
n
[
]
:
=
G
r
a
p
h
i
c
s
R
o
w
[
{
S
t
y
l
e
[
G
r
i
d
[
#
,
F
r
a
m
e
A
l
l
]
,
R
G
B
C
o
l
o
r
[
0
.
8
,
0
.
3
6
,
0
.
4
1
]
,
1
7
]
,
A
r
r
a
y
P
l
o
t
[
P
a
r
t
i
t
i
o
n
[
F
l
a
t
t
e
n
[
#
]
,
3
]
,
M
e
s
h
T
r
u
e
]
}
]
&
/
@
s
s
P
o
s
s
i
b
i
l
i
t
i
e
s
O
u
t
[
]
=
Looking at the models shown above, it's quite evident that these counter machines have a pattern; however, this pattern wasn't picked up by the
checkPattern
function. This means that ultimately, none of the 5 types of two-register counter machines produce a completely unpredictable counter machine.
Complexity with More Registers
Analyzing Three-Register Counter Machines
All possible two-register counter machines of the 5 types are predictable. However, a more complex counter machine could possibly be unpredictable. That means the logical next question is if adding more registers creates more complexity.
The first step is to analyze and compare the differences between 2 and 3 registers. The Minsky machine is best for this comparison, since it has the smallest number of possibilities to explore.
Create a two-register and three-register Minsky machine:
I
n
[
]
:
=
m
i
n
s
k
y
T
w
o
R
e
g
=
c
m
E
v
o
l
v
e
L
i
s
t
[
#
,
c
o
u
n
t
e
r
M
a
c
h
i
n
e
[
2
]
,
3
0
]
&
/
@
F
l
a
t
t
e
n
[
T
a
b
l
e
[
{
i
n
c
[
r
1
,
z
1
]
,
j
z
d
e
c
[
r
2
,
z
2
,
z
3
]
}
,
{
r
1
,
2
}
,
{
r
2
,
2
}
,
{
z
1
,
2
}
,
{
z
2
,
2
}
,
{
z
3
,
2
}
]
,
4
]
;
m
i
n
s
k
y
T
h
r
e
e
R
e
g
=
c
m
E
v
o
l
v
e
L
i
s
t
[
#
,
c
o
u
n
t
e
r
M
a
c
h
i
n
e
[
3
]
,
3
0
]
&
/
@
F
l
a
t
t
e
n
[
T
a
b
l
e
[
{
i
n
c
[
r
1
,
z
1
]
,
j
z
d
e
c
[
r
2
,
z
2
,
z
3
]
}
,
{
r
1
,
3
}
,
{
r
2
,
3
}
,
{
z
1
,
2
}
,
{
z
2
,
2
}
,
{
z
3
,
2
}
]
,
4
]
;
With this, the next step is to model a few Minsky machines to look for any similarities or differences.
Model the first 10 two-register and three-register Minsky machines:
I
n
[
]
:
=
m
T
w
o
=
m
i
n
s
k
y
T
w
o
R
e
g
[
[
1
;
;
1
0
]
]
;
m
T
h
r
e
e
=
m
i
n
s
k
y
T
h
r
e
e
R
e
g
[
[
1
;
;
1
0
]
]
;
G
r
a
p
h
i
c
s
R
o
w
[
{
A
r
r
a
y
P
l
o
t
[
P
a
r
t
i
t
i
o
n
[
F
l
a
t
t
e
n
[
#
]
,
3
]
,
M
e
s
h
T
r
u
e
]
}
]
&
/
@
m
T
w
o
G
r
a
p
h
i
c
s
R
o
w
[
{
A
r
r
a
y
P
l
o
t
[
P
a
r
t
i
t
i
o
n
[
F
l
a
t
t
e
n
[
#
]
,
4
]
,
M
e
s
h
T
r
u
e
]
}
]
&
/
@
m
T
h
r
e
e
O
u
t
[
]
=
O
u
t
[
]
=
Comparing the models, it becomes clear that the register values for two and three register Minsky machines are close to identical. The only differences are caused by the three-register Minsky machine having one more empty register. Hence, a reasonable hypothesis is that the register values for all two-register Minsky machines are identical to the register values for all three-register Minsky machines.
To prove this, the steps are: 1) finding the register values for all two-register and three-register Minsky machines, 2) eliminating 0's (as they represent empty registers), 3) deleting duplicates, and 4) checking if the resultant lists of two-register and three-register values are the same.
Follow the steps above for two-register and three-register Minsky machines:
I
n
[
]
:
=
m
i
n
s
k
y
T
w
o
V
a
l
u
e
s
=
D
e
l
e
t
e
D
u
p
l
i
c
a
t
e
s
[
T
a
b
l
e
[
F
l
a
t
t
e
n
[
m
i
n
s
k
y
T
w
o
R
e
g
[
[
n
,
A
l
l
,
2
]
]
]
/
.
0
N
o
t
h
i
n
g
,
{
n
,
L
e
n
g
t
h
[
m
i
n
s
k
y
T
w
o
R
e
g
]
}
]
]
;
m
i
n
s
k
y
T
h
r
e
e
V
a
l
u
e
s
=
D
e
l
e
t
e
D
u
p
l
i
c
a
t
e
s
[
T
a
b
l
e
[
F
l
a
t
t
e
n
[
m
i
n
s
k
y
T
h
r
e
e
R
e
g
[
[
n
,
A
l
l
,
2
]
]
]
/
.
0
N
o
t
h
i
n
g
,
{
n
,
L
e
n
g
t
h
[
m
i
n
s
k
y
T
h
r
e
e
R
e
g
]
}
]
]
;
m
i
n
s
k
y
T
w
o
V
a
l
u
e
s
m
i
n
s
k
y
T
h
r
e
e
V
a
l
u
e
s
O
u
t
[
]
=
T
r
u
e
Clearly, the values for two-register and three-register Minsky machines are identical. When the same steps are used to test the other 4 types of counter machines, the results are clear.
Check if two-register and three-register Shepherdson-Sturgis machines are identical:
I
n
[
]
:
=
s
s
T
w
o
R
e
g
=
c
m
E
v
o
l
v
e
L
i
s
t
[
#
,
c
o
u
n
t
e
r
M
a
c
h
i
n
e
[
2
]
,
3
0
]
&
/
@
F
l
a
t
t
e
n
[
T
a
b
l
e
[
{
i
n
c
[
r
1
]
,
d
e
c
[
r
2
]
,
c
l
r
[
r
3
]
,
c
p
y
[
r
4
,
r
5
]
,
j
n
z
[
r
6
,
z
1
,
z
2
]
,
j
[
z
]
}
,
{
r
1
,
2
}
,
{
r
2
,
2
}
,
{
r
3
,
2
}
,
{
r
4
,
2
}
,
{
r
5
,
2
}
,
{
r
6
,
2
}
,
{
z
1
,
6
}
,
{
z
2
,
6
}
,
{
z
,
6
}
]
,
8
]
;
s
s
T
h
r
e
e
R
e
g
=
c
m
E
v
o
l
v
e
L
i
s
t
[
#
,
c
o
u
n
t
e
r
M
a
c
h
i
n
e
[
3
]
,
3
0
]
&
/
@
F
l
a
t
t
e
n
[
T
a
b
l
e
[
{
i
n
c
[
r
1
]
,
d
e
c
[
r
2
]
,
c
l
r
[
r
3
]
,
c
p
y
[
r
4
,
r
5
]
,
j
n
z
[
r
6
,
z
1
,
z
2
]
,
j
[
z
]
}
,
{
r
1
,
3
}
,
{
r
2
,
3
}
,
{
r
3
,
3
}
,
{
r
4
,
3
}
,
{
r
5
,
3
}
,
{
r
6
,
3
}
,
{
z
1
,
6
}
,
{
z
2
,
6
}
,
{
z
,
6
}
]
,
8
]
;
s
s
T
w
o
V
a
l
u
e
s
=
D
e
l
e
t
e
D
u
p
l
i
c
a
t
e
s
[
T
a
b
l
e
[
F
l
a
t
t
e
n
[
s
s
T
w
o
R
e
g
[
[
n
,
A
l
l
,
2
]
]
]
/
.
0
N
o
t
h
i
n
g
,
{
n
,
L
e
n
g
t
h
[
s
s
T
w
o
R
e
g
]
}
]
]
;
s
s
T
h
r
e
e
V
a
l
u
e
s
=
D
e
l
e
t
e
D
u
p
l
i
c
a
t
e
s
[
T
a
b
l
e
[
F
l
a
t
t
e
n
[
s
s
T
h
r
e
e
R
e
g
[
[
n
,
A
l
l
,
2
]
]
]
/
.
0
N
o
t
h
i
n
g
,
{
n
,
L
e
n
g
t
h
[
s
s
T
h
r
e
e
R
e
g
]
}
]
]
;
s
s
T
w
o
V
a
l
u
e
s
s
s
T
h
r
e
e
V
a
l
u
e
s
O
u
t
[
]
=
F
a
l
s
e
Check if two-register and three-register Program machines are identical:
I
n
[
]
:
=
p
r
o
g
r
a
m
T
w
o
R
e
g
=
c
m
E
v
o
l
v
e
L
i
s
t
[
#
,
c
o
u
n
t
e
r
M
a
c
h
i
n
e
[
2
]
,
3
0
]
&
/
@
F
l
a
t
t
e
n
[
T
a
b
l
e
[
{
i
n
c
[
r
1
]
,
d
e
c
[
r
2
]
,
j
z
[
r
3
,
z
1
,
z
2
]
}
,
{
r
1
,
2
}
,
{
r
2
,
2
}
,
{
r
3
,
2
}
,
{
z
1
,
3
}
,
{
z
2
,
3
}
]
,
4
]
;
p
r
o
g
r
a
m
T
h
r
e
e
R
e
g
=
c
m
E
v
o
l
v
e
L
i
s
t
[
#
,
c
o
u
n
t
e
r
M
a
c
h
i
n
e
[
3
]
,
3
0
]
&
/
@
F
l
a
t
t
e
n
[
T
a
b
l
e
[
{
i
n
c
[
r
1
]
,
d
e
c
[
r
2
]
,
j
z
[
r
3
,
z
1
,
z
2
]
}
,
{
r
1
,
3
}
,
{
r
2
,
3
}
,
{
r
3
,
3
}
,
{
z
1
,
3
}
,
{
z
2
,
3
}
]
,
4
]
;
p
r
o
g
r
a
m
T
w
o
V
a
l
u
e
s
=
D
e
l
e
t
e
D
u
p
l
i
c
a
t
e
s
[
T
a
b
l
e
[
F
l
a
t
t
e
n
[
p
r
o
g
r
a
m
T
w
o
R
e
g
[
[
n
,
A
l
l
,
2
]
]
]
/
.
0
N
o
t
h
i
n
g
,
{
n
,
L
e
n
g
t
h
[
p
r
o
g
r
a
m
T
w
o
R
e
g
]
}
]
]
;
p
r
o
g
r
a
m
T
h
r
e
e
V
a
l
u
e
s
=
D
e
l
e
t
e
D
u
p
l
i
c
a
t
e
s
[
T
a
b
l
e
[
F
l
a
t
t
e
n
[
p
r
o
g
r
a
m
T
h
r
e
e
R
e
g
[
[
n
,
A
l
l
,
2
]
]
]
/
.
0
N
o
t
h
i
n
g
,
{
n
,
L
e
n
g
t
h
[
p
r
o
g
r
a
m
T
h
r
e
e
R
e
g
]
}
]
]
;
p
r
o
g
r
a
m
T
w
o
V
a
l
u
e
s
p
r
o
g
r
a
m
T
h
r
e
e
V
a
l
u
e
s
O
u
t
[
]
=
T
r
u
e
Check if two-register and three-register Successor machines are identical:
I
n
[
]
:
=
s
u
c
c
T
w
o
R
e
g
=
c
m
E
v
o
l
v
e
L
i
s
t
[
#
,
c
o
u
n
t
e
r
M
a
c
h
i
n
e
[
2
]
,
3
0
]
&
/
@
F
l
a
t
t
e
n
[
T
a
b
l
e
[
{
c
l
r
[
r
1
]
,
i
n
c
[
r
2
]
,
j
e
[
r
3
,
r
4
,
z
1
,
z