|
| |
|
|
A129835
|
|
A computation-universal sequence of natural numbers (with zero).
|
|
0
|
|
|
|
0, 1, 2, 3, 4, 5, 6, 0, 8, 9, 0, 1, 12, 13, 0, 1, 16, 17, 18, 0, 1, 21, 2, 23, 24, 0, 1, 27, 2, 29, 30, 31, 0, 1, 34, 2, 36, 2, 38, 39, 0, 1, 42, 2, 44, 3, 3, 47, 48, 0, 1
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
Let i be the index of an element (number) and f(i) be the number at that index. Applying f(f(...f(i)...)) until a fixed point is reached is computation - universal, i.e., can simulate the execution of any computer (Universal Turing Machine) program given proper choice of the initial i. The resulting fixed point encodes the program output, if any. The halting problem applies, so the procedure may not ever reach a fixed point.
The sequence results from using a modified version of the classical pairing function for nonnegative integers to numerically encode what is known as Combinatory Logic and is computation-universal, i.e. equivalent to the Turing Machine. Computationalist philosophers basically argue that each of us is inside that sequence, which the author personally doesn't believe. At least, lim f(x) on infinity is noncomputable.
|
|
|
REFERENCES
|
H.P. Barendregt, The Lambda Calculus, its Syntax and Semantics, revised edition, North-Holland, Amsterdam, 1984.
D. J. Cooke and H. E. Bez, Computer Mathematics. Cambridge University Press.
|
|
|
LINKS
|
|
|
|
FORMULA
|
Let d(x) = (1/2)x(x+1). Then the pairing function <x,y> = d(x+y)+x+2 maps pairs <x,y> onto numbers {2, 3, 4, ...}. To unpair a number q into x & y, follow these steps: if q >= 2 do p = q-2; n = FLOOR((sqrt(8p+1)-1)/2); x = p-d(n); y = d(n)+n-p; & now we know the x & the y in the paired representation of q = <x,y>.
This way we can represent any number in the form like, e. g., <<<1,0>,1>,<0,1>> = 323. To get that from 323, unpair 323 repeatedly until you have just 0's & 1's inside pairwise-balanced brackets. Next, define f(q) as follows: f(...<<<1,x>,y>,z>...)=...<<x,z>,<y,z>>..., else f(...<<0,x>,y>...)=...x..., else f(q)=q (fixed point).
Here we're doing pattern matching on the bracketed representations of numbers and changing one number into another in this representation according to the 3 rules above. Leading & trailing "..."'s are to be left the same. x, y, z match any subconstruction in q that then takes another place in the f(q) transformation.
The three rewriting rules are listed in descending priority, correspond to a single f(q) and should be applied to the first occurrence of the pattern in the bracketed construction. We operate on bracketed constructions with 0's & 1's that are in 1-to-1 correspondence with numbers and should be viewed as such.
Basically, f(q) is a relation on the infinite set of natural numbers (with zero) and can be viewed as an infinite directed graph with numbers as nodes connected by the relation j=f(q) that partitions the whole set into tree-like equivalence classes.
|
|
|
EXAMPLE
|
E.g. 323 corresponds to <<<1,0>,1>,<0,1>>: <<<1,0>,1>,<0,1>> <->
<<4,1>,<0,1>> <-> <21, 3> <-> 323 by the pairing transform. It reduces to
<0,1> by applying f(.): <<<1,0>,1>,<0,1>> -> <<0,<0,1>>,<1,<0,1>>> ->
<0,1>. The two "->"'s correspond to first applying the first rule, then
the second rule and then we get a fixed point <0,1> = 3 (by simply
pairing 0 & 1). At each step, we apply the first rule that applies, out of
the three. Taken together, this example shows that f(f(323)) = f(241) =
3. According to the 3rd rule, f(3)=3, so 3 is a fixed point - the
computation terminates at 3. The intermediate step
<<0,<0,1>>,<1,<0,1>>> = <<0,3>,<1,3>> = <8,13> = 241 by the pairing transform.
|
|
|
PROG
|
{ Turbo Pascal code for the SK - combinator - based Natural State Machine K == 0 S == 1 } program SKNSM; uses Crt, WinDos; (* Numerical pairing / unpairing routines *)
{2 naturals into 1} procedure Pair(X, Y : Comp; Shift : Byte; var P : Comp); var S : Comp; begin S := X + Y; P := S * (S + 1) / 2 + X + Shift; end;
{1 natural into 2} function UnPair(P : Comp; Shift : Byte; var X, Y : Comp) : Boolean; var N, T : Comp; begin if P >= Shift then begin UnPair := True; P := P - Shift; N := Int(((Sqrt(8 * P + 1)) - 1) / 2); T := N * (N + 1) / 2; X := P - T; Y := T + N - P; end else UnPair := False; end;
(* Combinatory routines *)
{parsing, get left} function CLGetLeftPart(C : string) : string; var I, Sum : Byte; begin if C[2] <> '(' then CLGetLeftPart := C[2] else begin I := 2; Sum := 1; repeat Inc(I); if C[I] = '(' then Inc(Sum) else if C[I] = ')' then Dec(Sum); until Sum = 0; CLGetLeftPart := Copy(C, 2, I - 1); end; end;
{parsing, get right} function CLGetRightPart(C : string) : string; var L, I, Sum : Byte; begin I := Length(C) - 1; if C[I] <> ')' then CLGetRightPart := C[I] else begin Sum := 1; repeat Dec(I); if C[I] = '(' then Dec(Sum) else if C[I] = ')' then Inc(Sum); until Sum = 0; CLGetRightPart := Copy(C, I, Length(C) - I); end; end;
{string to number} procedure CLEncode(C : string; var P : Comp); var X, Y : Comp; begin case C[1] of 'K' : P := 0; 'S' : P := 1; else CLEncode(CLGetLeftPart(C), X); CLEncode(CLGetRightPart(C), Y); Pair(X, Y, 2, P); end; end;
{number to string} procedure CLDecode(P : Comp; var C : string); var X, Y : Comp; begin if P = 0 then C := C + 'K' else if P = 1 then C := C + 'S' else begin UnPair(P, 2, X, Y); C := C + '('; CLDecode(X, C); CLDecode(Y, C); C := C + ')'; end; end;
{combinatory reduction / rewriting routine L - the cutoff number of reduction steps} function CLReduce(L : Comp; var P : Comp) : Boolean; var X, Y, XX, XY, XXX, XXY : Comp; begin if L = 0 then CLReduce := False else begin if UnPair(P, 2, X, Y) then begin if UnPair(X, 2, XX, XY) then begin if XX = 0 then begin P := XY; CLReduce := CLReduce(L - 1, P); end else if UnPair(XX, 2, XXX, XXY) then begin if XXX = 1 then begin Pair(XXY, Y, 2, X); Pair(XY, Y, 2, Y); Pair(X, Y, 2, P); CLReduce := CLReduce(L - 1, P); end else begin CLReduce := CLReduce(L, X); Pair(X, Y, 2, P); CLReduce := CLReduce(L - 1, P); end; end; end; end; end; end;
{reduce / rewrite ONCE} procedure CLRedStep(N : Comp; var R : Comp); begin CLReduce(1, N); R := N; end;
{reduction function - wrapper} function F(X : Longint) : Longint; var Y : Comp; begin CLRedStep(X, Y); F := Trunc(Y); end; (* Main routine *) const N = 299;
{first 300 pointers - a FSM prefix of NSM} var X, Y : Longint; TF: Text; begin Assign(TF, 'NSM.txt');
{file to write transitions to} Rewrite(TF); for X := 0 to N do begin Y := F(X); Write(TF, X, ' -> ', Y); if X = Y then Write(TF, ' FP');
{fixed point} WriteLn(TF); end; Close(TF); end.
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,more,uned
|
|
|
AUTHOR
|
Artem S. Shafraniuk (ashafraniuk(AT)gmail.com), May 21 2007
|
|
|
STATUS
|
approved
|
| |
|
|
