Analogia
Analogia is a syntax developed by User:ais523 in 2019 for describing a minimal/tarpit-like subset of analog computers. (It can thus be seen as a programming language – where the interpreter is either an analog computer, or else a program that simulates one – but analog computers were, of course, not invented by ais523.)
Syntax
An Analogia program consists of a number of integrators. These are the closest analogue that Analogia has to variables, being the only things whose values can change over time.
A program consists entirely of definitions of integrators. Each definition has the following form:
name = ∫ name + name + … + name ∂ name @ number
Names are basically just identifiers, and can consist of any string of characters other than control codes, whitespace, punctuation, ∫ and ∂ (although typically, you would use letters for this). Although it would be in keeping with the spirit of Analogia to allow numbers to be arbitrary real numbers, a concession is made to computability: Analogia implementations may specify their own set of supported numbers, although must support at least integers, written in decimal.
The syntax is flexible; horizontal whitespace can be omitted if the appropriate symbol (=∫, +, ∂, or @) is retained; or alternatively, the symbol can be omitted if some horizontal whitespace is retained. However, two integrator definitions must be separated by a sequence of whitespace containing a newline or formfeed, and this is mandatory. Comments are allowed, and run from # to the end of the line.
For example, the following two definitions are equivalent (although the first is much more readable!):
y = ∫y+y ∂x @1 # if x@0, then y = e**2x y y y x 1
The name t is special, and cannot be used as the name being defined in an integrator definition (i.e. it cannot appear immediately before the =∫). Circular definitions are allowed, i.e. an integrator may be defined in terms of itself, and two or more integrators may be defined in terms of each other. However, this does not apply to the ∂ term; any name appearing after ∂ must either be t, or else have been defined earlier in the program.
Specification
Implementing an Analogia program basically requires finding, for each integrator x = ∫ y1 + y2 + … + yn ∂z @ v, a function x from nonnegative real numbers to (possibly negative) real numbers, so that in the resulting set of functions, the following two constraints hold for each such function:
- Constant of integration: x(0) = v;
- Integral: x(t) is an indefinite integral of y1(t) + y2(t) + … + yn(t) with respect to z(t).
If t appears on the right hand side of an integrator definition, this refers to the identity function, i.e. t(t) = t.
Any integrators that are defined, but not used on the right-hand side of an integrator definition, are output integrators: the output of the program will be the function that the integrator represents (if there is more than one such integrator, the program will have multiple outputs). Likewise, any integrator names that are used on the right-hand side of an integrator definition, but never defined, are input integrators; the function that they represent is specified by the user. (In an actual mechanical analog computer, t is represented by the angular position of an axle that starts at 0 and is rotated at a constant speed by a motor, and thus increases at a constant rate over time; other inputs would then be specified by rotating a different axle to a position that represents the value of that function at the value of t. In an electronic analog computer, t is the passage of time in real life (measured in some convenient unit, e.g. seconds), and input functions would be specified by varying the voltage on an input over time.)
Computational class
ais523 believes that Analogia is at least Turing-complete (defining a halt event as, e.g., whether a particular output integrator's value ever drops below 0), but (as it deals with real numbers) is not certain that it is computable. It seems reasonable that numerical methods could be used to approximate the behaviour of a program, and thus it is likely that the language is computable, but it is unclear whether it's ever possible to bound the uncertainty caused by quantization errors (and thus to be able to confidently make statements about the behaviour of any given Analogia program up to a given time). (Note that physical analog computers will also accumulate errors over time, introduced via mechanical tolerances or electrical noise, and thus do not implement an "idealized" version of Analogia.)
The basic idea behind the proof that Analogia is Turing-powerful is to introduce a "quantization force" that adds a −sin(y) term into the value being integrated to produce y (it is easy to produce a sin operator using integrals). This means that, when y is not actively having its value changed, it will tend to converge to a multiple of 2π; this can be thought of as a "quantized integrator". This then makes it possible to, in effect, implement a digital computer on top of the analog computer, using a couple of quantized integrators as counters to produce unbounded storage and otherwise just making logic gates using values quantized to 0 or 2π. (Another way to think about this is that apart from the counters that are used to store unbounded amounts of data, the analog computer is simulating the circuitry of a digital computer, which is theoretically analog and reliant on quantization to keep the behaviour deterministic and history-independent.)