# Blindfolded Arithmetic

Possibly a fairly easy language to start off with, relatively
speaking.  (There are limits on how difficult a language I can make
because I have to prove it Turing-complete myself!)

For this language, the program set is the set of Blindfolded
Arithmetic programs as given in the section "program" below, the input
set is the set of positive integers, and the output set is the set of
integers (the entire set, not just the positive integers).

This language is fairly interesting – maybe even practically useful –
because it has a more or less total lack of control flow, being
entirely based on computations on numbers you can't see.  That makes
it potentially useful as a language for implementing programs inside
[homomorphic encryption](https://en.wikipedia.org/wiki/Homomorphic_encryption)
systems.

# Specification

Blindfolded Arithmetic is an esoteric programming language with the
following specifications:

## Data storage

A state of a running Blindfolded Arithmetic program consists of six
variables, each of which can store an integer.  (There are no limits
on how large or small these integers can get; in particular, they can
go negative.)  The variables are called `a`, `b`, `c`, `d`, `e`, and
`i`.

At the start of the program, `a` to `e` inclusive are each initialised
to 0, and `i` is initialised to a positive integer taken from user
input.  (If no input is available, `i` is initialised to 1.)

If the program ceases execution (this can only occur due to division
by zero), the value of `i` immediately before the division was
attempted is used as the program's output.

## Program

A Blindfolded Arithmetic program is a list of commands, each of which
has one of the following forms (where *v* can be replaced by any
variable name, potentially a different name each time it's used):

* *v* `=` *v* `+` *v*
* *v* `=` *v* `-` *v*
* *v* `=` *v* `*` *v*
* *v* `=` *v* `/` *v*

Note that each operand of the commands *must* be a variable; this
language does not allow the use of literal integers.

Execution of the program is performed by running each of the commands
in sequence, and then looping back to the start and continuing to run
the commands in sequence again, ad infinitum (or until there's an
attempt to divide by zero, which ends the program).

Each command has the same semantics as you'd expect from the notation,
which is no different from that used by most practical programming
languages: the values of the second and third variables metioned in
the command are taken, an arithmetic operation
(add/subtract/multiply/divide respectively for the four forms of
command) is applied to them, and the resulting value stored into the
first variable.  Division here is integer division, rounding
towards 0.

There is no control flow of any kind, other than program exit; the
commands always cycle in sequence, up until a division by zero (if
any) occurs and ends the program.  In particular, there's no way to
directly read variables, only to use them as a source of calculations
whose results impact the values assigned to other variables.

# Computational class

We can prove this language Turing-complete by translating Minsky
machines into it.  We'll use a formalization of Minsky machines with
three counters (of which counter C contains the initial input), and
the following set of commands, each of which is formed from a
condition and an action:

* **Conditions**
  * run unconditionally
  * run if *counter* is 1; do nothing if the value is 2 or greater;
    undefined behaviour if the value is 0
* **Actions**
  * increment *counter*
  * decrement *counter*; decrementing 0 or 1 is undefined behaviour
  * goto location X
  * halt, outputting the value in counter C minus the value in counter A

It's fairly obvious that any Minsky machine can be written in this
form (you need to start off by unconditionally incrementing counters A
and B, then you simply treat a value of 1 as your "zero point" and
never let the counters go lower).  The limited conditionals can be
made into arbitrary conditionals by conditionally running a goto
command.  Two counters is enough for Turing-completeness, but for
noninteractive-IO-completeness (which is what the question wants), we
need either three counters or a more complex I/O encoding.  It's
simplest to use three counters so that we don't have to pack and
unpack the I/O encoding.

`e` is used as the instruction pointer, pointing to the active command
in the Minsky Machine program.  This is initially 0, so we need to
zero-index our commands (i.e. the first command is IP 0).  We use only
even numbers for instructions (with odd-numbered instruction pointers
conceptually pointing to implicit "no-op" commands).  Additionally, we
make it undefined behaviour to run off the end of the program (this is
not a problem as you could just put an unconditional goto there).

The counter values are stored in `a` (A), `b` (B), and `i` (C).
Counter C is never allowed to reach zero (except temporarily for very
brief periods).  `c` is used as a flag to determine if the command
should run.  `d` is used as a temporary.

The basic idea is to write the implementation of each Minsky command
in sequence, where each command is implemented such that if `e` has a
particular value, it will mimic the effect of that command, and if `e`
does not have that value, the implementation will do nothing.  Each
command starts off the same way, by setting `c` to 1 if `e` has a
given value *N* and 0 otherwise:

* `d = i / i` (now `d` is 1)
* Do `e = e - d` *N* times (now `e` is 0 iff `e` = *N*)
* `c = e + e` (now `c` is 0 iff `e` = *N* and even)
* `c = c + c` (now `c` is 0 iff `e` = *N* and a multiple of 4)
* `c = c + d` (now `c` is 1 iff `e` = *N*, else ≥5 or ≤-3)
* `c = d / c` (now `c` is 1 iff `e` = *N*, else 0)
* Do `e = e + d` *N* times (restoring it to its original value)

Next, we determine if the condition matches.  If the condition is "run
unconditionally", we have nothing to do.  Otherwise, we want to set
`c` to 0 (regardless of its previous value) if the counter in question
has a value greater than 1. The below is shown for counter A, but you
can consistently replace `a` with `b` or `i` to get the implementation
of the other two nontrivial conditions:

* `d = d / a` (now `d` is 1 if `a` = 1, otherwise 0)
* `c = c * d` (now `c` is 1 if both `e` = *N* and `a` = 1, otherwise 0)

Most of the commands now have an obvious implementation.  To increment
a counter (if the right command is running and the condition if any is
met), we add `c` to `a`, `b`, or `i` as appropriate.  To decrement a
counter, we subtract `c` from the relevant variable.  To do a goto
command, we repeatedly do `e = e - c` or `e = e + c` to adjust the
instruction pointer by the required offset.  None of these commands
will do anything if `c` is 0, of course.  (Note that for goto, we jump
to the no-op just before the target command, so that we never end up
with two commands running in the same program iteration; this isn't
technically necessary but is the simplest implementation to prove
correct.)

To implement the fairly complex conditional halt, we do this:

* `d = i / i` (now `d` is 1)
* `d = d - c` (now `d` is 0 if a halt is required, 1 otherwise)
* `i = i - a` (now `i` is the value we'd want to output)
* `d = d / d` (division-by-0 if a halt is required, otherwise no-op)
* `i = i + a` (restores the value of `i`)

Note that the complexity is required so that we can output the entire
range of integers, not just the positive integers, as required by the
problem specification and the choice of the integers as the output
set.

At the end of the Blindfolded Arithmetic program, we need to move onto
the next Minsky Machine command for the next iteration.  That looks
like this:

* `d = i / i` (now `d` is 1)
* `e = e + d`

Note that we're only adding 1 at a time to `e`, in case we just ran a
goto instruction.  This means that while we aren't doing gotos, only
every second iteration will do anything interesting.  That isn't a
problem; the next command in the program will still run eventually,
and Turing-completeness proofs don't care about performance.