Dear reader, this is my first post in this forum, as a consequence of a quick interaction with the Twitter account @WolframResearch.
The main purpose is to verify the computational irreducibility of the behavior described by the algorithm I'm going to introduce here. So I hope in a response from some "A New Kind of Science" expert.
But the algorithm, neatly varying factors, generates the increasing sequence of positive numbers, in the context of my study about an infinite-dimensional discrete space; so discussion of other aspects you possibly find interesting will also be welcome.
var F
F = function ( Limit )
{
var Coordinates
var Expand
var Index
var Numbers
var Quantity
var Value
Numbers = new Array ( )
Numbers [ 0 ] = 1
Expand = function ( Coordinate )
{
var Index
var Quantity
var Value
Quantity = Coordinate . Exponents . length
Value = Coordinate . Base - 1
while ( Value -- )
for ( Index = 0 ; Index < Quantity ; ++ Index )
Coordinate . Exponents [ Coordinate . Exponents . length ] =
Coordinate . Exponents [ Index ]
++ Coordinate . Exponents [ Coordinate . Exponents . length - 1 ]
}
Coordinates = new Array ( )
Coordinates [ 0 ] = new Object ( )
Coordinates [ 0 ] . Base = 2
Coordinates [ 0 ] . Exponents = new Array ( )
Coordinates [ 0 ] . Exponents [ 0 ] = 0
Coordinates [ 0 ] . Exponents [ 1 ] = 1
for ( Quantity = 1 ; Quantity < Limit ; ++ Quantity )
{
Value = 0
for ( Index = 0 ; Index < Coordinates . length ; ++ Index )
{
if ( Coordinates [ Index ] . Exponents . length <= Quantity )
Expand ( Coordinates [ Index ] )
Value += Coordinates [ Index ] . Exponents [ Quantity ]
}
if ( ! Value )
{
Coordinates [ Index ] = new Object ( )
Coordinates [ Index ] . Base = Quantity + 1
Coordinates [ Index ] . Exponents = new Array ( )
for ( Value = 0 ; Value < Quantity ; ++ Value )
Coordinates [ Index ] . Exponents [ Value ] = 0
Coordinates [ Index ] . Exponents [ Value ] = 1
}
Numbers [ Quantity ] = 1
for ( Index = 0 ; Index < Coordinates . length ; ++ Index )
for ( Value = 0 ; Value < Coordinates [ Index ] . Exponents [
Quantity ] ; ++ Value )
Numbers [ Quantity ] *= Coordinates [ Index ] . Base
}
return Numbers
}
That is an ECMA-262 definition of the algorithm, that generates, up to a given limit, the sequence of all the positive numbers by neatly selecting the respective prime factors.
This means every JavaScript programmer can try it copying the code in an HTML document, as part of a suitable JavaScript tag.
To understand it imagine a table showing in each row a positive number and the exponents of the powers of its prime factors...
positive number | power of 2 | power of 3 | power of 5 | power of 7 | power of 11
----------------+------------+------------+------------+------------+------------
1 | 0 | 0 | 0 | 0 | 0
----------------+------------+------------+------------+------------+------------
2 | 1 | 0 | 0 | 0 | 0
----------------+------------+------------+------------+------------+------------
3 | 0 | 1 | 0 | 0 | 0
----------------+------------+------------+------------+------------+------------
4 | 2 | 0 | 0 | 0 | 0
----------------+------------+------------+------------+------------+------------
5 | 0 | 0 | 1 | 0 | 0
----------------+------------+------------+------------+------------+------------
6 | 1 | 1 | 0 | 0 | 0
----------------+------------+------------+------------+------------+------------
7 | 0 | 0 | 0 | 1 | 0
----------------+------------+------------+------------+------------+------------
8 | 3 | 0 | 0 | 0 | 0
----------------+------------+------------+------------+------------+------------
9 | 0 | 2 | 0 | 0 | 0
----------------+------------+------------+------------+------------+------------
10 | 1 | 0 | 1 | 0 | 0
----------------+------------+------------+------------+------------+------------
11 | 0 | 0 | 0 | 0 | 1
It is well known that 6, for example, is the result of 2^13^15^0*7^0.
7 == 2^03^05^0*7^1
8 == 2^33^05^0*7^0
9 == 2^03^25^0*7^0
The algorithm doesn't create the table by factoring positive numbers; instead it is capable to generate the sequence of exponents in each column following a rule so that the result of multiplying all the factors represented in a row is in a strictly increasing order with respect to the one of the succeeding row.
All that implies "discovering on the fly" the primes needed to get bigger results gradually.
The Numbers array is just to allow a simple verification of the correctness of the algorithm; in fact, for each of its elements, the following condition must occur... Numbers[Index]==Index+1
Each element of the Coordinates array corresponds, in a sense, to a column of the imagined table.
Such an element is an object for which the Base property represents the prime factor while the Exponents property represents, as an array, the column of exponents to which to rise that prime.
Coordinates[0] is a sort of "seed element". In fact the code dynamically produces all the data needed to show a table with as many rows as the given Limit value.
The Expand function is invocated every time the "insufficient currently available data" condition is reached.
The line of code...
if ( ! Value )
... is where the "next prime needed" condition is checked.
Of course every time a new prime number is involved in the data structure all the exponents, except the last one, of its "corresponding column" must be set to 0.
In the trials the max value for Limit depend on the memory available for the JavaScript interpreter and its efficiency.
At the moment I'm not interested about the innumerable ways to optimize the implementation of the algorithm... but it is important to keep in mind that it is implementable in a fashion that dynamically takes advantage of mass memory as its availability increase.
If needed to better understand what I've exposed here the following two online reference documents can be consulted...
http://www.comprendonio.info/I/UnlimitedInside/I/Spazio%20discreto%20ad%20infinite%20dimensioni.Txt
http://www.comprendonio.info/I/UnlimitedInside/I/Sequenza%20notevole%20di%20coordinate.Txt
Anyway my main concern is to get confirmation about my strong suspect that the behavior described by this algorithm is not computationally reducible.
