Talk:Adar
Computational class
The obvious way one would go to prove Adar's Turing completeness by reduction, would be using The Amnesiac From Minsk or The Waterfall Model, which both have very similar semantics.
Now, both TAFM and TWM rely on being able to modify a specific counter by a value, and not all the counters. (In fact, if one were to make a subset of TWM where the zeroing trigger must be the same for every waterclock, it'd be easy to compile that to Adar).
So, Adar has no way of only changing the value of one register; in fact, an Adar program acts as a single, shared register that just has many different triggers.
Which means it probably isn't Turing complete. However, its true computational class is still unknown. TuxCrafting (talk) 07:49, 9 June 2019 (UTC)
- I have shown that Adar can simulate zeroing triggers that are not the same for every iteration, which shows that it could possibly compile to the TWM. --
A (talk)11:28, 12 June 2019 (UTC)
Adar is a finite-state machine. It's equivalent to a single, shared register whose possible values (from -∞ to +∞) are divided into a number of different regions, each of which add a different number to the register that cycle. Only two of these regions are infinitely large. If the number to add from an infinitely large region moves towards the infinity it contains, or stays in place, there's no computational value for that region because it'll trivially go into an infinite loop. If the number to add in both regions moves away from the infinity it contains, only finitely many values of the register will be accessible. In either case, for either region, the language is a finite-state machine. Ais523 non-admin (talk) 12:31, 10 June 2019 (UTC)
- (in reply to a post by User:A which was deleted after I posted this) Assuming you have a language that's a universal push-down automaton, you can compile Adar to it, but you can't compile it to Adar. The same would be true if you replaced Adar with any other language that's a universal finite-state machine. --ais523 20:29, 10 June 2019 (UTC)
- The terminology around language class vs. "programs in a language" seems unclear, especially in regards to FSMs. "Adar is a finite-state machine" seems incorrect for the language, but pretty clearly you meant its class is that of being able to simulate any FSM, and that's what the wiki's Category:Finite_state_automata appears to signify. In other words: any Adar program is a FSM. For Turing completeness there is an accurate term: a machine that can simulate any other Turing machine is called universal. You used the term "universal finite-state machine", which sounds right, but then apparently those don't exist because the 'universal' part means it can't be finite, which makes sense when you think about it. There are infinite possible FSMs, so anything that can simulate all of them can't be finite. Ref: this short paper agrees, which I found when looking for standard terminology.
- I don't know the correct term for a language or machine that can simulate any FSM, but even so, Adar can implement infinite looping counters (and infinitely many of those since the step can be different), which are beyond the capability of an FSM. I think I agree that it doesn't give a "computational" advantage, but it's clearly able to store more information, which counts for something. An observer could (potentially) tell how long an Adar program has been running for, or how many times its FSM was triggered, where a plain FSM could not because it only stores state. I think this makes (at least some) Adar programs single register wikipedia:Counter machines (1CM), but I can't find much information on these because they seem pretty useless compared to 2CMs which get all the press. By definition 1CMs are FSMs with one register, which seems to match Adar. Practically, I agree with pretty much everything ais523 has said, so I'm just trying to sort out the subtleties. I'm expecting that 1CMs are possibly "computationally" equivalent to FSMs using strict technical definitions, even though 1CMs capture more information, and would like some confirmation or comments on these thoughts. Salpynx (talk) 10:37, 11 June 2019 (UTC)
- I guess the way to think about it is in terms of how much data a program can read, not how much it can write. Adar can only read a finite number of different shared-counter values, as can 1CMs. It can write more values than that, but only by going beyond a point of no-return, at which point the program has conceptually halted already; the entire future progress of the program is entirely predictable, and any values that may exist within the counter are all effectively equivalent to each other.
- There's something of an interesting conceptual point here (compare, e.g., Blindfolded Arithmetic), but it's hard to pin it down into words. --ais523 15:48, 11 June 2019 (UTC)
Does the "old" version of Adar contribute anything to the computational class? See this page. The "old" version used triplets instead of pairs of registers, and the second number was the trigger of the register. This version uses relatively free syntax compared with the "current" version, which restricts the second number to 0. --A (talk) 10:34, 12 June 2019 (UTC)
The syntax of the "old" version allows the triggers to be different; i.e. you can conditionally trigger registers. For example, picture a program in the "old" version that contains a looping counter with a series of negative registers that are waiting to be triggered. If a list of accumulators are negative numbers and one is less than the other, they will be triggered conditionally in a order that was pre-defined, which could help Adar to simulate conditional statements and simulating waterfalls in The Waterfall Model. TuxCrafting has shown that "In fact, if one were to make a subset of TWM where the zeroing trigger must be the same for every waterclock, it'd be easy to compile that to Adar"; the "old" version allows the trigger to be different, because the "old" version allows registers to be triggered in a syntax that is more free, which helps the trigger to be different.--A (talk) 11:03, 12 June 2019 (UTC)
- The revised version can also do that. I have already shown that the two are equivalent (since the value of a register never leaks out of the register definition anyway, so its base value can be anything without changing semantics), with the trigger value being nothing more than syntactic sugar. TuxCrafting (talk) 11:07, 12 June 2019 (UTC)
I have been wondering what sorts of things can be "computed" with Adar and I've tried a few simple programs. To me, Adar is reminiscent of a cellular automaton where every cell/register is in the neighborhood of all others. (The oscillator and stabilizer examples reinforce this impression). I think a mathematician would consider an Adar program to be a dynamical system. Since the first register determines the state of the entire program and the next step is determined completely by the current step, an Adar program is a single-parameter function from the set of integers to itself. Running the program just iterates this function and produces a sequence of integers. It seems reasonable then to consider the result of the computation to be either the sequence of values taken on by the first register or the final value of some register (for a program that halts). So my initial question becomes "what sequences can an Adar program compute?"
The oscillators section shows how to generate some cyclic sequences. A small modification and extension of one of the other examples can compute an arbitrary number of powers of 2: [(1, 1), (-1, 1), (-2, 1), (-3, 1), (-4, 1), (-5, 1), (-6, 1), ... (-max, -2*max-1)]. (If an infinite set of registers following this pattern could be specified, then such a program could enumerate powers of 2 until halted). In fact, powers of N can be computed in a similar way: [(1, n-1), (-1, n-1), (-2, n-1), (-3, n-1), (-4, n-1), (-5, n-1), ...]. Perhaps it is possible to produce any polynomial-based sequence?
A more interesting question might be "what sequences CAN'T an Adar program compute?" I'm pretty sure that it can't produce the digits of an irrational number, at least if it must output the exact digits and not larger numbers that contain the digits. This observation can be generalized: since the next number in the output sequence depends only on the previous, it should not be possible to produce any sequence in which an integer N is followed by two different numbers in different places.
Any other observations? -- Anthonykozar (talk) 04:15, 30 November 2021 (UTC)
Syntactic Sugar
Hmm, I think it is not appropriate syntactic sugar; that is, I don't think that the updated version can simulate a looping counter that counts down to a positive number. Also, the initial values has to be different.--A (talk) 11:13, 12 June 2019 (UTC)
- If you mean that you can't make a counter from 10 to 0 in the revised version, that's true; however, you can make a counter from 9 to -1, which has the exact same behavior: trigger 10 times, adding -1 each time, and then halt. What counts isn't the register's absolute value but its relative value wrt its trigger value (which is fixed to 0 in the revised version). TuxCrafting (talk) 11:19, 12 June 2019 (UTC)
Request for a different form for oscillators
You have said that "of course it's possible to make oscillators with a different form", but every oscillator I make was covered by the formula. May you add another form for oscillators here? --A (talk) 12:51, 11 June 2019 (UTC)
- It's pretty trivial how to make an oscillator with a different form. For example,
[(0, {step}), (-{step * (period - 1)}, -{step * period - n}), (-{step * (period - 1)}, {n})]wherenis any integer, generates oscillators (by partially cancelling the effect of the second tuple). While Salpynx's form can generate an oscillator for any given step and period, it certainely isn't the only way to make oscillators. TuxCrafting (talk) 12:45, 11 June 2019 (UTC)