General blindfolded arithmetic

Blindfolded Arithmetic is a programming language where there are a finite but arbitrary amount of expressions which can operate on six variables. Programs are a list of ordered assignment expressions which always execute, all inside an infinite loop. General blindfolded arithmetic is a generalized approach to the problem of ascertaining the computational class of these sorts of languages.

Core model

A blindfolded model has some number of operators. For instance, canonical blindfolded arithmetic has the operations +, -, *, // (truncating division). The model also has some number of variables which are initialized to some value at the start. All variables have values which belong to some specific set, usually either ℤ (as in canonical BA) or ℚ (as in Imprecision). Finally, there is also an ordered list of assignment instructions, which can be in the form A = B (copy the value of B into A) or A *= B for any operator * (operate A * B then put the value into A). Canonical blindfolded arithmetic is equivalent to this, and general expressions can also be decomposed into this system using storage variables. Additionally, there is some halt condition. This can either be the result of a variable being assigned some value, or an operator being used on some certain value.

General to canonical

A = B    is    A = B + 0
         or    A = B - 0
         or    A = B * 1
         or    A = B / 1
A *= B   is    A = A * B    for any operation *

For canonical to general, v = a * b for any operation * can be decomposed like so:

T = a
T *= b
v = T

As such, canonical blindfolded arithmetic is an instance of general blindfolded arithmetic where there are the operators +, -, *, //, variable values are in the set ℤ, there are a maximum of six variables, and the halt condition is when A //= B is run with B = 0. Further, this decomposition method (which works in general) means that any canonical program can be translated into a general program which uses at most 7 variables, 6 for each of the canonical variables, and one temporary one.

This model can be recomposed back into a more expressive form where variables can have updates consisting of complex expressions. In fact, since everything occurs unconditionally, updates relating variables can be rolled back up to the start of the loop. Every general blindfolded arithmetic program with n variables can be replaced with an equivalent one consisting of n simultaneous updates, or n updates to n temporary variables with n assignments to the real variables.

Viewing programs in this way makes it more clear how the model relates to other computational models. The most similar models are dynamical systems, where a set of expressions are applied to realize updates of existing variables. There are other similar systems like Petri nets, vector addition systems, polynomial register machines, rational and integer maps, and many others.

ℤ with +, -, * (at least FSM)

Consider the general system where there are an unlimited number of variables which belong to the set of integers. It does not seem immediately obvious how to do much at all. However, the multiplication instruction with the collapsing behavior of A * 0 = 0 and the fact that 1² = 1 allows for the implementation of NAND. If values are in the set {0, 1} then a * b is equivalent to AND:

a b   a * b
0 0   0
0 1   0
1 0   0
1 1   1

Still under the use of variables in the set of 0 and 1, boolean inversion can be done using 1 - a:

a     1 - a
0     1
1     0

This allows us to construct NAND with 1 - a * b.

We can decompose any stateful logic boolean system into a stateless one which feeds into itself at the very end. This can be done in a number of ways, but one possible option is to view the logic machine as being between two unlimited sets of pins. The bottom pins serve as inputs from the last iteration, and the top pins serve as outputs to the next. In between, since we have NAND, we can construct any feed-forward boolean logic circuit. Then, using the iteration feedback, we can hold onto arbitrary state. Since the pins must be addressed explicitly in the program (since they are simply variables), and the program is finite, this construction by itself is in the class of finite state automata.

Of course, the variables are not in the set {0, 1}. We can however force them to be by only ever using the NAND construction and having 0 and 1 be the only constants, but that is not required. Indeed, we can infinitely increment and decrement any number of variables we'd like depending on the state of the FSM, suggesting that it is possible to implement counter machines. The existing FSM construction would serve as the control structure, with the increment/decrement variables being the counters. We can already conditionally increment counter += 1 NAND some_cond and decrement counter -= 1 NAND some_cond the counters. The only question is if we can somehow read the state of the counters.

If we are to continue using the NAND construction in our counter construction, then we would somehow need to construct some counter system where there are infinitely many reachable states which map to a certain value, and a single reachable state which maps to a different value. These values should be in the set {0, 1}. If such a construction exists, it likely would involve multiple variables and the use of hysteresis.

This requirement that infinite states map to a single one, and there is one other identifiable one can be referred to as normalization or collapse. There are many different collapsing operators we could add to this system to immediately make it Turing complete using counters. If we have some operator norm which ignores the left hand side and normalizes the right A norm= B being A = norm(B) which returns 0 if B is zero, and 1 otherwise, for B in the nonnegative integers, testing the value of a counter and operating the FSM based on it is trivial.

Immediately Turing complete additions

The following are definitions of the norm function using common functions/operators (each line is equivalent):

The signum function

sgn(a)
sign(a)
signum(a)

C-style comparisons (where true is 1 and false is 0)

a != 0
1 - (a == 0)
a > 0
1 - (a < 1)
a >= 1
1 - (a <= 0)

Truncating division (such that 5//2 = 2) and modulo

1 - (1 // (a + 1))
1 mod (a + 1)

Absolute value (almost)
This shifts the counter over. -1 is now the 0 value.
Further, the function either returns 1 for 0... or -1 for the 0 value.
It's not immediately obvious how to map this negative logic to the normal 0/1 logic, however, it can be done with division.

1 - (abs(x) - x)

Absolute value with any division
This works by (-1, 1) -> (0, 2) -> (0, 1) due to 0/2 = 0, 2/2 = 1.

((1 - (abs(x) - x)) + 1) / 2
(2 - abs(x) + x) / 2

Constructible is able to implement the above with sqrt(x * x) as abs(x).

In general, if there is some function which produces either -1 or 1 then adding 1 and dividing by two results in 0 or 1, with -1 → 0, 1 → 1.

Known constructible functions

Any periodic sequence can be reproduced by this instance of GBA. To do so for a sequence with period n, construct a binary counter which properly loops after n. Then create indicator variables which use NOT and AND to return 1 only if a certain value is in the binary counter. These indicators indicate if the current index mod n is some residue. For each m of the n terms, create a variable which multiplies the indicator for that index with m. Finally, add up all of these together. The final addition is the current value of the sequence. Using this, any periodic function of an infinite counter can also be constructed. When the counter is incremented, increment the periodic function's binary counter. When the counter is decremented, decrement the binary counter. Potentially notable periodic functions of a counter may include modulo.

Evenness logic

The logic above can actually be generalized to accept any arguments, if we perceive values as just their value mod 2. This is covered on EvenOdd, but if we apply mod 2 to the inputs of the AND and inversion functions we get the same effective functions, but any integer value may be passed in, with even values considered false and odd true. Since modulo distributes and is idempotent, applying modulo to the arguments is equivalent to applying modulo to the output, and is in turn (for a long chain of logical functions) equivalent to applying modulo to the very last output. It also has the effect that sign is meaningless, and any type of offset by 1 is inversion.

If we think about the values that variables will hit as a chain of logic goes on, we can observe that all falsy values will have a 2 in their prime expansion, whereas all truthy values will have none, that is, false values are in the form $2^{n}\cdot k$ with truthy being $2^{0}\cdot k$ for arbitrary n and odd k. If we assume that false values have a single 2 then we can create a counter which conditionally increments by multiplying by a logic output and conditionally decrements by dividing by a logic output. The value of the counter is the exponent of 2, with even (false) values affecting changes to it. The counter can be used directly in logic operations, since it is even (false) whenever it is 1 or higher, and odd (true) when it is at 0.

The issue with this construction is ensuring that the inputs to the counter have at most 1 two in the expansion. This can be satisfied by a pre-norm function. A definition for this function can be given in terms of modulo 2. A value mod 2 will be 0 for evens, and 1 for odds, so offsetting this by 2 will result in 2 for evens and 3 for odds. This preserves evenness and reduces values into either $2^{1}$ or $3^{1}$. If we want the counter to be purely a power of two at all times we can invert the mod term, resulting in odds being 1.

2 - (n mod 2)

We can define x mod 2 in terms of pi with cos or sin for use with the above:

(1 - cos(pi * x)) / 2
(1 - sin(pi * x + pi / 2)) / 2

The greatest common divisor function can also implement mod 2:

gcd(n, 2) - 1

Note that the function 2^x is effectively norm if we consider it mod 2. That is, it returns odd for 0 and even for all positive values. This suggests that this exponential function may be Turing complete.

Equivalence to ℚ with /

(At least non-lowest terms) rationals can be expressed using a pair of variables, one variable each for the numerator and denominator.

# reciprocal
num' = den
den' = num

# multiply, for divide reciprocate b
num' = num_a * num_b
den' = den_a * den_b

# add, for subtract multiply num_b by -1
num' = (num_a * den_b) + (num_b * den_a)
den' = den_a * den_b

This should allow for this GBA to represent any value that a GBA on ℚ with rational division can.

Notably, if there were a general modulo operator then the floor function could be made using:

num' = num - num % den
den' = den

The ceil function could be made similarly. This suggests that ℤ with +, -, *, % is Turing complete, from the arguments below for why ℚ with +, -, *, /, floor is.

This construction has interesting properties if zero denominators are allowed. Performing a/b * c/0 results in (a*c)/0 as expected. However, addition a/b + c/0 results in (c*b)/0. This means that split rational numbers with 0 denominators form a sort of fixed region, with 0/0 being a fixed point. A consequence of allowing zero denominators is that we can define a function on the counter which maps all points to 1 except for 0, which gets mapped to this fixed point 0/0. The fixed point is notable, and we may refer to it as NaN, after the floating point NaN. It has the following properties (and more):

NaN + r = NaN
NaN * r = NaN
NaN - NaN = NaN

Perhaps more interesting is that we can define a function which maps 0/0 to 1, and k/k to a different kind of 1. If we multiply the top and bottom by some constant, say 2, then we get 0*2/0*2 = 0/0, 2k/2k. The non-NaN value has its top and bottom at least 2 away from 0. If we then subtract one from the top and bottom it results in 0-1/0-1 = -1/-1, 2k-1 / 2k-1. 2k is never 1, so 2k-1/2k-1 is never NaN, and it is also always positive in the numerator and denominator. While this type of 1 has an interesting underlying notation, it doesn't have unusual properties under the definitions above. Do note that -a/-b + -b/-c = e/f, whereas if only one of the two sides is one of these negative positives, -a/-b + b/c = -e/-f, a/b + -b/-c = -e/-f, similar to with multiplication.

Removal of -

Similarly to how we can represent rationals as a pair of variables, we can have a GBA on $\mathbb {Z} _{0}^{+}$ with + and * and represent negatives as a pair of numbers, like a - b. If a = b, then it is 0, if a > b positive, a < b negative. Here are the operations:

# addition
pos' = pos_a + pos_b
neg' = neg_a + neg_b

# inversion by * -1, which works with the addition
pos' = neg
neg' = pos

# multiplication
# (p_a, n_a) * (p_b, n_b)
# definition of split negatives
# (p_a - n_a) * (p_b - n_b)
# FOIL
# p_a*p_b - p_a*n_b - n_a*p_b + n_a*n_b
# pull out common coefficients
# p_a*(p_b - n_b) - n_a*(p_b - n_b)
# distribute positive coefficients
# (p_a*p_b - p_a*n_b) - (n_a*p_b - n_a*n_b)
# definition of split negatives
# (p_a*p_b, p_a*n_b) - (n_a*p_b, n_a*n_b)
# invert right into its negation number
# (p_a * p_b, p_a * n_b) + (n_a * n_b, n_a * p_b)
# add components
# (p_a * p_b + n_a * n_b, p_a * n_b + n_a * p_b)
pos' = pos_a * pos_b + neg_a * neg_b
neg' = pos_a * neg_b + neg_a * pos_b

With split rationals we were able to perform the otherwise impossible 1 / 0, reaching a fixed point "NaN." All values for pos and neg in $\mathbb {Z} _{0}^{+}$ are valid and have no special properties. We can still alter the components in ways which violate the addition/subtraction/etc. constraints above. If we still have access to - we can access actual negatives, but observe their actions are equivalent to split negative operations:

-k -  j = -1(k + j) =  0      - (k + j)
 pos' = 0
 neg' = pos + neg

 k - -j =    k + j  = (k + j) - 0
 pos' = pos + neg
 neg' = 0

-k - -j =   -k + j  =  j      - k
 pos' = neg
 neg' = pos

Attempted solutions to the norm problem

One approach is that there could be two counters, one being conditionally shifted over by 1, such that counter - lag = 1 when counter is nonzero. If this exists, it would serve as the norm function. Incrementing a counter with its lag can be done by incrementing the counter unconditionally, but only incrementing lag if the difference is one:

counter += 1
lag += counter - lag

Decrementing the counter is trivial. counter -= counter - lag. Lag, however, needs to also be decremented in a way that preserves the norm property, it needs to only ever decrement when it is not zero. It needs to somehow identify if it is zero using its own state and the counter. This attempt simply shifts the norm problem onto another variable.

Relation with Diophantine equations

Using the undecidability of Diophantine equations, we can show that the general termination problem of this model is undecidable. Suppose the halting condition is that the variable halt is set to 0. We can then have a program which assigns halt to the result of a polynomial on the inputs. This construction has a trivial halting problem since every loop repeats its state, simply check if halt is assigned 0 and you have solved the halting problem. However, the termination problem is undecidable. This is due to the MRDP theorem which showed that there cannot exist an algorithm which says if any given Diophantine equation has solutions. Determining if halt is never set to zero for any inputs is equivalent to asking if a parameterized Diophantine equation has solutions.

This also provides us with another method to produce a universal blindfolded arithmetic machine. The MRDP theorem was proven by showing that any recursively enumerable set has a corresponding Diophantine equation, such that the solutions of the equation are the same elements of the set. It has also been shown that there are universal Diophantine equations, which can emulate the behavior of any Diophantine equation through the use of a program parameter.

Using this fact we can produce systems with undecidable halting problems. Suppose we have a general blindfolded arithmetic system which halts like the prior one we used to prove the undecidability of the termination problem. As it stands, while the termination problem is undecidable, the halting problem is trivially decidable. However, suppose we only have the parameters of the Diophantine equation as inputs to the machine. The unknowns will begin with all zeroes, and the machine sets the unknowns to a new combination each iteration. If the algorithm used to produce a new combination can reach every combination of integers, then this machine will only halt when the Diophantine equation is solved. Since Diophantine equations can be created which have solutions for values which cause Turing machines to halt, this program for this instance of GBA has an undecidable halting problem, and is also Turing complete, at least for semi decidability.

A program of this form would have two sections: the polynomial halt test, and the unknowns updater. The polynomial halt test is a straightforward implementation of the Diophantine equation. The unknowns updater somehow takes the current tuple of unknowns and produces a new tuple. While repeats do not harm the power of this model, the update procedure must be able to produce all allowable combinations of unknowns.

For one unknown, this is trivial. Simply increment the unknown each iteration for unknowns in the naturals, otherwise multiply a sign variable by -1 and increment a variable every other iteration, with the unknown being sign * step for the integers. For multiple unknowns, it's not so simple. A procedure for the naturals in Python could be:

# iterated
fast += 1
halt(slow, fast)
if fast == slow:
    slow += 1
    fast = 0

Which could be extended to any number of variables. Thus proving again that a GBA with == is Turing complete. It is unclear how to implement an algorithm which updates a tuple of unknowns in GBA with just + and *. Since there exists a 9 unknown (in the naturals) universal Diophantine equation, an algorithm which updates only 9 natural valued unknowns would be sufficient to show Turing completeness.

ℚ with +, -, *, / (at least FSM)

If division is added there are some interesting properties that hint at potential solutions to the normalization problem. The division operator here is rational division, and is nearly closed except for 1 / 0 which is undefined and programs which utilize it are invalid. The semantics between this instance of GBA and Imprecision are identical.

Of course, from the prior section, arbitrary stateful boolean logic can be constructed, allowing for the construction on any FSM we desire. The issue of reaching infinite readable state remains.

Consider that x / x = 1 for all x other than 0. Additionally note that x * (1 / x) has the same values. We may be able to break a counter variable into two, the counter and anticounter, such that counter * anticounter = 1 for nonzero counter, and 0 for zero counter. Incrementation could be accomplished with:

counter += 1
anticounter = 1 / counter

Since counter is never -1, this always works. Decrementation is more difficult. We want some ℚ² function which has the following mappings:

(0, k) → (0, j) (for any k/j)
(1, 1) → (0, k) (for any k)
(2, 1/2) → (1, 1)
(3, 1/3) → (2, 1/2)
(n, 1/n) → (n-1, 1/(n-1))

Assume we had some function which for 0, 1, 2, 3, 4... was 0, 0, 1, 1, 1... Call this function indicator. If we had such a function then the counter could be decremented according to the mapping:

indicator = magic_indicator_fn(counter, anticounter)
decrement = counter * anticounter    # don't decrement if at 0
counter -= decrement
anticounter = indicator / (counter + (1 - indicator))

So how can this indicator be constructed? Observe the differences between counter and anticounter

counter       0      1      2      3      4      5   ...
anticounter   0      1      1/2    1/3    1/4    1/5 ...
difference    0      0      3/2    8/3   15/4   24/5 ...

The only time the difference is nonzero is when the indicator is active. Now consider repeated squaring of these values, according to

difference = difference * difference
difference = difference * difference
difference = difference * difference
...

For some large number of repetitions. Since there is a suitably large number of repetitions, the values greater than one tend to infinity, with the ones at 0 of course remaining there:

squared       0      0        ∞      ∞      ∞      ∞ ...

We can then perform a number of operations:

1 - x         1      1       -∞     -∞     -∞     -∞ ...
1 / x         1      1       -ɛ     -ɛ     -ɛ     -ɛ ...
1 - x         0      0        1      1      1      1 ...

Which is the indicator function. Decrementation could then be done as:

indicator = 1 - (1 / (1 - (counter - anticounter)**k))
decrement = counter * anticounter
counter -= decrement
anticounter = indicator / (counter + (1 - indicator))

For some constant power k, which we can achieved by iteratively squaring counter - anticounter.

If k is "infinity" then this works, the value of the indicator function is exactly as we require. If k is simply "some large constant" then there will be error introduced. This error depends on the distance from the 0 point, with lower numbers having worse error. The question of if this specific system is Turing complete depends on the question of if the error can be controlled in programs which may increment and decrement arbitrarily, and if the logic indicator function counter * anticounter has a low enough error for the logic system to reliably operate as the FSM. Ideally, error would able to converge to some zero value.

With pow

If there were a right integral pow operator (also often called ** or ^), the k term in the above could be variable and incremented, doubled, squared, or even exponentiated every iteration of the program. Experimentation suggests this could be convergent and could interface with the existing logic system.

Potentially this could even be done without a pow operator. Perhaps the to-the-power-k term could be taken to some constant power every iteration of the program. However, if it is reset every decrement then the k is mostly just some constant.

A potential argument for why a variable power k would be Turing complete is that the error produced by the FSM and decrement should only ever get worse by some constant each iteration. We therefore expect the error function to be linear. The pow operation with a k that increases superlinearly should outpace the linear error. This argument might also be useful to show that this method does not work for a constant k, since linear error should outpace a constant.

If the operator accepted any rational right arguments then it would be Turing complete by implementation of abs by sqrt.

A simpler infinity

The approach of using repeated squarings to achieve "infinity" is promising and can be used to create a simpler norm function. Observe the following operations:

       0   1   2   3   4...
x*2    0   2   4   6   8...
x^2^k  0   ∞   ∞   ∞   ∞...
1-x    1  -∞  -∞  -∞  -∞...
1/x    1  -ε  -ε  -ε  -ε...
1-x    0 1+ε 1+ε 1+ε 1+ε...

We can define norm(a) to be 1 - (1 / (1 - ((a * 2)**j))) where j is in the form 2^k for a constant k. We can implement this exponentiation by repeatedly squaring k times. Note that (2*a)^2^k tends to 0 as k increases for a < 1/4, and tends to infinity for greater (for nonnegative a). Additionally note that the infinities and epsilons are all different. The infinity corresponding with norm(1) is the smallest, with its epsilon the largest.

We can define logic using the norm function:

a   b    a * b
  ε   ε  ε^2
  ε 1+ε  ε+ε^2
1+ε   ε  ε+ε^2
1+ε 1+ε  1+2ε+ε^2

We can norm this to get:

a   b    norm(a*b)
  ε   ε  ε
  ε 1+ε  ε
1+ε   ε  ε
1+ε 1+ε  1+ε

Assuming that ε+ε^2 < 1/4.

We can also define inversion. Typical inversion is non functional:

a    1-a
  ε  1-ε
1+ε   -ε

The norm of these are both ε. However, recall that norm(1) is the largest epsilon. Call that ε₁. This is a different inversion function, evaluated with the worst case:

a     1-a+ε₁
  ε₁  1
1+ε₁  2ε₁

And the typical:

a     1-a+ε₁
  ε   1+ε
1+ε   ε₁+ε

The norm of this function norm(1-a+ε₁) is inversion assuming that 2ε₁ < 1/4.

# norm, j in the form 2^k for constant positive integer k
norm(v) = 1 - (1 / (1 - ((v * 2)**j)))
# this must be less than 1/4
worst_epsilon = norm(1) - 1

# AND, assuming normalized a, b
and(a, b) = norm(a * b)

# NOT, assuming normalized a
not(a) = norm(1 - a + worst_epsilon)

Assuming the demands of this model can be guaranteed by the repeated use of the norm function in the logic definition, this model is Turing complete as it allows for unbounded counters to be read and written to according to an arbitrary control mechanism.

Take k to be 1, resulting in a power of 2^1 = 2. This is the lowest value which still exhibits the normalizing behavior we want. If we repeatedly apply norm to 0 we get 0, same for any value below about 0.21. If we repeatedly apply norm to 1, we get 1.207... If we subtract 1 from this we get some epsilon, the worst one. The epsilon is the same as the norm threshold, below it repeated norm tends to 0, above it repeated norm tends to 1 + epsilon. We can use this epsilon to improve the accuracy of the machines we build using this norm construction. If we structure our control system such that every variable passes through n norms, then we can use an epsilon which is produced by applying norm to 1 n-1 times and subtracting 1 to get a correcting epsilon. The outputs of the machine have this epsilon subtracted.

While this drastically improves the error, allowing for even low powers in the norm function to be practical for machines operating with billions of increments/decrements, it's unclear if this method diverges or not. Testing seems to suggest it does not, but actual proofs would be ideal.

Immediately Turing complete additions

Of course, any of the additions for the previous model would make this model Turing complete as well. Particularly applicable is the sqrt function, as in Constructible.

When using the split counter such that counter * anticounter = 1 except at 0, the rounding functions can be used to create an indicator function for 1.

floor(anticounter)
ceil(anticounter - 1/2)
round(anticounter - 1/3)              # for half even, half up, half down
round(anticounter + 1/3)              # for towards zero
(round(anticounter - 3/4) + 1) / 2    # for away from zero, round end of 0 or 5 away from zero

This function is 1 at 1 and 0 everywhere else. Since counter * anticounter is 0 at 0 and 1 everywhere else, we can combine them to get the indicator.

not_zero = counter * anticounter
is_one = floor(anticounter)    # or equivalent
is_zero = 1 - not_zero
is_zero_or_one = is_zero + is_one
indicator = 1 - is_zero_or_one

If we define k / 0 to be 0 for all k then a norm function for a given counter is simply counter / counter.

Summary

Function(s)	Lower bound	Upper bound	Exact valued TC?	Class note	Equivalent models	Dynamical system
$\mathbb {Z} _{0}^{+}$
+	unknown	unknown	unknown		$\mathbb {Z}$ + -	Affine discrete time, space
+ and *	FSM	TC?	unknown	FSM by implementing logic	$\mathbb {Q}$ + - * /	Polynomial discrete (rational) time, space
$\mathbb {Z} _{0}^{+}$ + *, and one of these
signum	TC	TC	yes	can form a one-hot function
//	TC	TC	yes
abs	TC	TC	yes
mod	TC	TC	yes	equiv to $\mathbb {Q}$ w/ floor
mod 2	TC	TC	yes
gcd	TC	TC	yes
comparisons	TC	TC	yes	C-style == etc.
pow	FSM	TC?	no?
$\mathbb {Q}$ + - * /, and one of these
floor	TC	TC	yes
ceil	TC	TC	yes
round	TC	TC	yes
/0	TC	TC	yes	division where k/0 is defined to equal 0
$\mathbb {R}$ + - * /, and one of these
sqrt	TC	TC	yes
sin	TC	TC	yes
cos	TC	TC	yes

GBA is a particular modeling of discrete time dynamical systems. Discrete time dynamical systems are equivalent in power to iterated difference systems, which are discrete time variants of differential equations. They are also called recurrence systems.

In terms of loops, GBA models single-path (deterministic) loops. GBA $\mathbb {Z}$ with + and * models polynomial integer or rational loops, while other instances model other types of loops. The type of halting condition for the instance determines additional qualities of the loop. Imprecision for instance models single-path polynomial integer/rational loops without guards, and with inequality conditions.

Determining if GBA with + and * is related to the problems of determining if polynomial over integer, discrete time dynamical systems have certain semantic properties, like:

• Reachability (does the system eventually reach a certain vector of values, or within some range, for the variables?)
  • Skolem problem (does the trajectory of a (linear) dynamical system go through zero?)
  • Kannan-Lipton Orbit problem (does the trajectory of a (linear) dynamical system go through a given point?)
• Boundedness (under some norm, does the vector eventually explode to infinity?)
• Mortality (does the system reach a certain vector/range for all initial configurations?)
• Skolem-Pisot problem (does the trajectory of a dynamical system intersect a hyperplane?) is similar to reachability on ranges and the boundedness problem
• Positivity problem (does a dynamical system always stay positive?)
  • By flipping signs, this is equivalent to the halting problem for Imprecision

Notably, if the system is Turing complete, then all of these (generalized) interesting properties should be undecidable due to Rice's theorem, which generalizes the halting problem. Many of these questions are decidable for linear loops (which means they are decidable for GBA $\mathbb {Z}$ with +). It is hinted that undecidability exists for polynomial (GBA $\mathbb {Z}$ with + and *) loops, but these statements are rarely accompanied by citation.

Literature review:

• Integer loops (which are broadly equivalent to GBA + *) are variously undecidable
  • By adding:
    • An isPositive() function (which is the same as the norm function above)
      • This is well proven in this article, and also the literature
    • Integer floor division (which implements isPositive)
    • Truncated subtraction (again, implemening isPositive)
    • isPositive() can be implemented and multiplexed if the loop has two bodies which are executed conditionally on a variable
  • isPositive() cannot be implemented under an integer linear constraint model
    • isPositive() can be implemented under such a model equipped with an arbitrary irrational number
    • integer linear constraint models can implement Petri nets (which are decidable)
• Dynamical systems are undecidable for many general questions
  • Many different undecidable models of computation can be modeled as dynamical systems
  • Dynamical systems can implement Turing machines using piecewise functions with modulo
    • As noted prior, piecewise functions suffice, as does modulo, separately
• Reachability for linear dynamical systems is decidable
  • Continuous time case
  • Discrete time case on integers although this does require some circumstances, but there aren't known undecidable results for this case
• Certain questions about polynomial loops are undecidable
  • Like if they contain invariants
• Reachability computation for polynomial dynamical systems is possible, at least if overestimating
  • Using hypershapes is common "due to undecidability"
• Chaotic systems, like Turing machines and dynamical systems, can be analyzed statistically
  • By analyzing their behavior under different coding schemes
  • Using transients
• Difference systems on certain rings are known universal, undecidable
  • Sequences (may be uncomputable?)
• Some of the problems above are undecidable in circumstances which may be emulable by GBA
  • Boundedness between all products of two matrices is undecidable
  • As is pairwise k-matrix mortality (if two matrices multiply to the zero matrix in at most k matrix multiplications) for certain matrices
• Differential equations are undecidable
  • A robust Turing machine can be implemented in them
  • But not all differential equation forms may implement them
  • Notably, they can be uncomputable "super-Turing"
  • But some universal ones are computable, the Graça et al. machine implies robustness to noise due to implementation on discrete computers
    • This machine may indeed be applicable to GBA, and a restricted, computable Analogia
• The termination problem for polynomial integer loops is undecidable, as is for linear loops with polynomial conditions
  • This is a direct consequence of the MRDP theorem stating that Diophantine equations cannot have a general solution algorithm
• Termination problems for certain polynomial loops is decidable
  • Triangular weakly nonlinear (twn) in $\mathbb {R}$ the discrete cases $\mathbb {Z}$ and $\mathbb {Q}$ are at least semi-decidable

The present principle author of this page, User:stkptr, must note that they have not read through all of these papers in their entirety. This is mainly due to their unfamiliarity with certain fields of mathematics. Due to this, one or more of these papers may prove GBA Turing complete, or decidable.

Example languages

These languages can be viewed as instances of general blindfolded arithmetic.

Unknown upper bound computational class

• Imprecision (ℚ with +, -, *, /)
• Insanity seems equivalent to Imprecision, just without a defined halting condition
• Spam (ℤ with +, -, * and variable jump)
• Analogia may be viewable as an instance on ℝ with operators from calculus

Turing-complete

• Blindfolded Arithmetic (ℤ with +, -, *, //)
• Constructible (ℚ with +, -, *, /, sqrt)

See also

• Universal approximation theorem (Wikipedia) which states that any function can be approximated by a neural network using non-polynomial activation functions