My Unreliable Past

My Unreliable Past is an esoteric programming language created by User:ais523 in 2014. It explores philosophical questions about the nature of program startup and termination. Other than that, it is quite similar to (but not identical to) Fractran.
== Semantics ==
Data in a My Unreliable Past program are stored in one of 24 variables, each of which can hold an arbitrary nonnegative integer (providing infinite storage through the use of bignums). These variables are each named using letters (specifically, all the capital letters in the English alphabet apart from J and V).
There are basically three operations that can be performed on these variables: adding constants to them, subtracting constants from them, and testing them for zero. A test for zero succeeds if the variable happens to be zero at the time, and fails otherwise; it never changes the value of the variable. Subtracting a constant from a variable fails if it would become negative, and succeeds (changing the value accordingly) otherwise. Adding a constant to a variable always succeeds (and changes its value accordingly).
Commands are grouped into transactions; there can be up to 32 commands in any single transaction. Running a transaction is, in most cases, equivalent to running all the commands in it in sequence. However, if any command within the transaction fails, the effects of all the commands that ran so far in the transaction are reversed, reverting the value of every variable back to the value it had at the start of the transaction, and the remaining commands are not run. Thus, a transaction only does anything if all the commands in it succeed. A single-command transaction is identical to the command itself (and in fact, My Unreliable Past does not really distinguish between these two cases).
A My Unreliable Past program consists of a circular sequence of transactions.
== Syntax ==
A My Unreliable Past command is written using a capital letter, then either + or - followed by a positive number (for a command that adds or subtracts a constant), or else =0 (for a zero test). Commands within a transaction are separated with commas; transactions are separated from each other with semicolons. In order to fit a My Unreliable Past program into a text file (which has a beginning and an end), it is acceptable to pick an arbitrary point within the program and break the program there, in order to make it into a linear rather than circular sequence of bytes.
For example:
 +67; O=0, O+66; O=0, O
is a valid My Unreliable Past program. (It's possible to move any number of characters from the start to the end, or vice versa, without changing the meaning of the program.)
Whitespace is disallowed between the digits of a number, but otherwise permitted anywhere. Anything between opening and closing parentheses is a comment, and ignored; comments nest. All programs must contain at least one transaction, and an equal number of opening and closing parentheses (otherwise, it would be conceptually ambiguous as to whether any arbitrary program was entirely commented out, or not, because there is no point equivalent to the start of the program that can be known to be definitively outside all comments). No syntax not mentioned here is allowed, and a My Unreliable Past interpreter should reject programs that contain syntax errors.
== Input and output ==
The variables I and O are special, in that they can change value "spontaneously". If at any time (except in the middle of a transaction) O holds a nonzero value, then after a random number of transactions have succeeded or failed, its value will be set to zero. When this happens, one Unicode character is written to standard output, whose codepoint is the value that O had just before it was zeroed, minus one. Similarly, if at any time (except in the middle of a transaction) I holds a zero value, then after a random number of transactions have succeeded or failed, one Unicode character will be read from standard input, and the value of I will change to that character's codepoint, plus one. Once standard input reaches end-of-file, I will continue these spontaneous changes from zero, but will reuse previous input, repeating the entirety of the input that was previously seen indefinitely. If no bytes are available (either due to end-of-file on standard input before any characters were read, or because standard input is blocking and waiting for more input), the program continues running; I simply fails to spontaneously change while waiting for more input. (Likewise, if a program is incapable of outputting due to an output pipe being full or similar problem, O will not spontaneously change until the output pipe becomes writable again.)
== Program execution ==
When a My Unreliable Past interpreter starts up, each variable starts with a random integer, determined via the following algorithm: there is a 1 in 2 chance the variable is initialized to 0; a 1 in 4 chance the variable is initialized to 1; a 1 in 8 chance the variable is initialized to a 2-bit integer (picked uniformly in the range 2 to 3); a 1 in 16 chance that the variable is initialized to a 3-bit integer (picked uniformly in the range 4 to 7), and so on. (The pattern continues indefinitely, meaning that all integers have a nonzero chance of being chosen.)
The program itself, unsurprisingly, starts running with a random transaction. From then on, the transactions run in sequence, succeeding and changing variables or failing and leaving them alone, indefinitely (because the program forms a loop, and has no endpoint).
== Computational class ==
My Unreliable Past is somewhat hard to classify. It is trivial to compile Fractran (that does not use too many prime factors) into a hypothetical version of My Unreliable Past that starts at a known point in the program, with known variables (and thus misses the point behind the language); you can use one variable for each prime factor in the Fractran program, and one more as a sentinel to record whether any changes have been made this cycle. This makes deterministic-startup My Unreliable Past Turing complete (even without the use of zero tests). However, the randomized startup means that literally any internal state the program reaches during normal operation is also a potential startup state, and thus a My Unreliable Past program can never know anything for certain about its past execution; any data it calculates will, to the very next transaction, potentially have been placed there randomly rather than having been calculated by the program.
As such, the best that a My Unreliable Past program can do is to restart calculations every now and then, getting further and further each time. Any program that wants access to unbounded storage (and thus potentially needs to perform complete loops in order to access memory) inevitably runs the risk of producing the "wrong" answer for whatever job it's trying to perform. However, it is possible to write a program which, if it ever produces a wrong answer, will follow up with an infinite number of correct corrections. (Such a program must also have the potential to output incorrect corrections, but those themselves can be corrected infinitely many times.)
It is impossible for a My Unreliable Past program to ever effectively halt. For instance, if there were any circumstances under which such a program, say, produced no more output indefinitely, it would be possible for the program to start up in that "halt" state, meaning that the program never produced any output ever. Thus, a program that wants to be "reliable" must keep performing the same calculations over and over again, ad infinitum, purely out of paranoia that everything it believes is wrong.
== Examples ==
=== Hello, world! ===
This program outputs "Hello world!" with high probability, along with the potential for outputting a random character at the beginning of the string. After outputting, it loops indefinitely, doing nothing.
 (Set A to 100 with high probability... around 1/589 chance of failure)
 A-0,A=0,A+100;
 A-1,A=0,A+100;A-2,A=0,A+100;A-3,A=0,A+100;
 A-4,A=0,A+100;A-5,A=0,A+100;A-6,A=0,A+100;
 A-7,A=0,A+100;A-8,A=0,A+100;A-9,A=0,A+100;
 A-10,A=0,A+100;A-11,A=0,A+100;A-12,A=0,A+100;
 A-13,A=0,A+100;A-14,A=0,A+100;A-15,A=0,A+100;
 A-16,A=0,A+100;A-17,A=0,A+100;A-18,A=0,A+100;
 A-19,A=0,A+100;A-20,A=0,A+100;A-21,A=0,A+100;
 A-22,A=0,A+100;A-23,A=0,A+100;A-24,A=0,A+100;
 A-25,A=0,A+100;A-26,A=0,A+100;A-27,A=0,A+100;
 A-28,A=0,A+100;A-29,A=0,A+100;A-30,A=0,A+100;
 A-31,A=0,A+100;A-32,A=0,A+100;A-33,A=0,A+100;
 A-34,A=0,A+100;A-35,A=0,A+100;A-36,A=0,A+100;
 A-37,A=0,A+100;A-38,A=0,A+100;A-39,A=0,A+100;
 A-40,A=0,A+100;A-41,A=0,A+100;A-42,A=0,A+100;
 A-43,A=0,A+100;A-44,A=0,A+100;A-45,A=0,A+100;
 A-46,A=0,A+100;A-47,A=0,A+100;A-48,A=0,A+100;
 A-49,A=0,A+100;A-50,A=0,A+100;A-51,A=0,A+100;
 A-52,A=0,A+100;A-53,A=0,A+100;A-54,A=0,A+100;
 A-55,A=0,A+100;A-56,A=0,A+100;A-57,A=0,A+100;
 A-58,A=0,A+100;A-59,A=0,A+100;A-60,A=0,A+100;
 A-61,A=0,A+100;A-62,A=0,A+100;A-63,A=0,A+100;
 A-64,A=0,A+100;A-65,A=0,A+100;A-66,A=0,A+100;
 A-67,A=0,A+100;A-68,A=0,A+100;A-69,A=0,A+100;
 A-70,A=0,A+100;A-71,A=0,A+100;A-72,A=0,A+100;
 A-73,A=0,A+100;A-74,A=0,A+100;A-75,A=0,A+100;
 A-76,A=0,A+100;A-77,A=0,A+100;A-78,A=0,A+100;
 A-79,A=0,A+100;A-80,A=0,A+100;A-81,A=0,A+100;
 A-82,A=0,A+100;A-83,A=0,A+100;A-84,A=0,A+100;
 A-85,A=0,A+100;A-86,A=0,A+100;A-87,A=0,A+100;
 A-88,A=0,A+100;A-89,A=0,A+100;A-90,A=0,A+100;
 A-91,A=0,A+100;A-92,A=0,A+100;A-93,A=0,A+100;
 A-94,A=0,A+100;A-95,A=0,A+100;A-96,A=0,A+100;
 A-97,A=0,A+100;A-98,A=0,A+100;A-99,A=0,A+100;
 (Output the characters one at a time, keeping track of where we are with A)
 A-100,A=0,O=0,O+73,A+101;A-101,A=0,O=0,O+102,A+102;A-102,A=0,O=0,O+109,A+103;
 A-103,A=0,O=0,O+109,A+104;A-104,A=0,O=0,O+112,A+105;A-105,A=0,O=0,O+33,A+106;
 A-106,A=0,O=0,O+120,A+107;A-107,A=0,O=0,O+112,A+108;A-108,A=0,O=0,O+115,A+109;
 A-109,A=0,O=0,O+109,A+110;A-110,A=0,O=0,O+101,A+111;A-111,A=0,O=0,O+34,A+112;
== See also ==
* Lost
Category:LanguagesCategory:Low-levelCategory:UnimplementedCategory:2014
Category:Unknown computational classCategory:ProbabilisticCategory:Nondeterministic