Noise automata
A Noise automata, abbreviated NA is a deterministic model of computation made by User:RainbowDash that computes through finding patterns in random data. NAs work via the very same ideas seen in Ramsey theory.
Specification
A Noise Automata takes in an input seed and a generation number. It repeatedly applies a function to the seed, step by step, and stops once it reaches the specified generation. At that point, the machine outputs the result of the function at that generation.
Noise automatons can be simplified into a 2D function. where is the input and is the stopping generation or “index” and is some transformation using and . For all inputs, there is an index such that a desired function is simulated to some finite precision. This is what the output of the computer is and thus how it calculates.
While the function in a Noise Automaton is to be normally represented as a two-dimensional function , it is not limited to only two inputs. In general, may accept multiple inputs beyond the normal input and index , and can be extended accordingly to accommodate additional parameters. But, for clarity and simplicity, the remainder of this writing will focus on the two-dimensional form .
Ramsey theory & Fundamental Application
Ramsey theory states that given enough random data you can find any pattern you want, this is the core of why NAs can compute any finite sequence.
The name "Noise automata" comes from the similarity between them and random number generators, which produce streams of random digits from a given seed. In this analogy, the seed acts as the input, and the number of generations represents the index. In this way, a Noise Automaton can be built using a PRNG: by running it for a certain number of steps (the index), you can find an output that matches the desired function for a given input. An issue arises however, in not knowing which generation gives the the correct function. To solve this, you can create another program to search through the output space for the desired function. Once the correct index is found, the NA can then reproduce the result by running the PRNG for that many generations.
In this we see that your random number generator creates patterns, and sometimes those patterns just happen to be a function you are looking for. The less precise you want your function to be, the higher of a chance you find your function given lower amounts of random numbers or data in Ramsey theories case.
It should be noted that the function that a Noise Automaton uses does not inherently have to be random. The Noise Automaton could just as easily iterate through a finite function space in a fashionable order. However, there is no reason on why the function can not be some PRNG or other function of the alike.
Computational class
Noise automatons are considered Total because, for every possible input, they produce a corresponding output.
NAs can also be situated within the domain of hypercomputation, depending on the definition of the function that governs their behavior. To illustrate this, define as an infinite-term polynomial. By doing so, one can specify any real-valued input x∈R, allowing the function to operate over an uncountably infinite domain.
is further extended such that it includes real numbers capable of encoding solutions to the Halting Problem. Through this, NAs can achieve hypercomputational power
On the topic of calculating all functions f(x)
In the function the set of all elements in must be a totally ordered set, because must increment each step in certain running conditions of this machine. Having that be said, must have a cardinality that is equal to or more than the set of all functions of in order to calculate and index all functions . That means, if we want to calculate all functions for both and can not both use the same symbol set.
