# Use NVM to tenaciously resume operation whenever aborted

## Summary

The aim of this challenge is to write a tenacious program. This is a stateful program designed to output a given string, but for which, if the program is aborted at any point during the writing of the string, rerunning the program will continue where it left off, writing only the characters that have not been written so far.

Specifically, the goal of this challenge is to output the string 01 using a tenacious program.

## Background

I once conjectured that with n cits, any string up to length 2(n-k) could be ouptut by a tenacious program, for some small fixed k. I'm now leaning toward thinking the goal can't be achieved :-(

This challenge, therefore, was designed to determine whether tenacious programs that output nontrivial strings are possible. 01 appears to be the shortest nontrivial goal string, and so is the subject of this challenge.

Current status: So far there are no correct answers, but it has been proven that 2 cits are not enough.

## Data storage

In order to store information across multiple runs of the program, you have access to a number of cits, bits made out of non-volatile memory; these are persistent, stateful bits that can have the value 0, 1, or undefined. They have the value 0 before the first execution of the program. If the program is aborted midway through writing a cit, that cit's value becomes undefined (unless the value being written to the cit was the value previously stored there), and will remain undefined until the program writes a 0 to the cit (and is not aborted midway through the write). Reading an undefined cit will (unpredictably) produce 0 or 1 (maybe different for each read), and your program must function correctly regardless of what values are read from undefined cits.

Each cit used by your program has a distinct address, which is an integer (you may choose how many cits are used, and what their addresses are). In order to read and write from the cits, you may assume that you have access to two functions: a function that takes a constant integer (representing the address of a cit), and returns a value read from that cit; and a function that takes an integer (representing the address of a cit) and a boolean (representing the value of a cit), and writes the value to the cit. These functions are guaranteed return in finite time (unless the program is aborted while they are running).

You may choose the names of this functions as appropriate for the language you are using. If the language uses identifiers as function names, the recommended names are r to read, w to write.

## Output

Due to the possibility that the program will be aborted during output, output from this challenge works a little differently from normal. Output may only be done a character at a time. You have access to a function that produces output in the following way: its argument is 0, 1, 2, or 3; if the given argument is the same as the argument to the previous call of the function (even in a previous execution of the program), or is 0 and no output has ever been produced, then the function does nothing. Otherwise, it outputs 0 if given an argument of 0 or 2, or 1 if given an argument of 1 or 3.

You may choose the name of this function as appropriate for the language you are using. If the language uses identifiers as function names, the recommended name is p.

## Requirements

Write a program with the following properties:

• The only state used by the program between runs is a number of cits (as defined above); all other storage used by the program must be initialised to a fixed value at the start of each run.
• The program will terminate in finite time, unless aborted.
• If all the cits used by the program start with value 0, and then the program is run, aborted after an arbitrary length of time (which could occur at any moment during the program's execution, even while writing a cit or writing output), run again, aborted after another arbitrary length of time, and this process is repeated until the program terminates naturally, then (no matter what timing was used for the aborts) the combined output from all the program executions will be 01.
• The program is single-threaded, making no use of parallelism or concurrency (this is required for the abort behaviour to be well-defined).

(More generally, a "tenacious program" is any program with the properties above, with 01 replaced with any arbitrary string. But this challenge is just about writing a tenacious program to output 01.)

Alternatively, a proof that such a program is impossible is also considered a valid submission to this challenge.

You may alternatively write a function instead of a program, but it is only allowed to store state between calls via using cits; it cannot look at any of the state of the program that called it.

## Example

Here's an example of a C program that fails to solve the challenge:

// uses one cit with address 3
#include "hal.h"            // assumed to define r(), w(), p()
int main(void) {            // entry point, no parameters or input
if (r(3)==0)            // cit 3 read as 0, that is state 0 or undefined
w(3,0),             // write 0 to cit 3, to ensure it's defined
p(2);               // put 2 with output '0' initially
w(3,1),                 // mark we have output '0'
p(1);                   // put 1 with output '1'
}                           // halt


To see why this doesn't work, imagine that the first run of the program is aborted during w(3,1): this outputs 0, and causes cit 3 to become undefined. Then imagine that the second run happens to read the undefined cit as 1, and is aborted after p(1) completes (but before the program ends); at this point, the output is 01. The cit is still undefined, because writing 1 to an undefined cit does not define it (only writing 0 can define it). A third run of the program might now happen to read the undefined cit as 0, thus causing 0 and 1 to be output again. This produces the output 0101, which is not 01.

## Checking the validity of your solution

@hammar has written a checker that determines whether a given solution is valid (and/or explains why a particular solution isn't valid). To check your own solutions, or to see how it works, you can Try it online!.

## Victory condition

The program that achieves the requirements above using the fewest cits wins. In the case of a tie, programs which make fewer writes to cits per program execution are considered better (with the worst case more important than the best case); if there is still a tie, the shortest program (not counting the declarations of the provided functions) wins.

• I feel like a similar question was asked - perhaps relating more to flash memory/power surges, I think - but I can't seem to find it. – Gaffi Apr 26 '12 at 17:31
• @Gaffi: I made a question two weeks ago asking a program with similar properties for decimals of Pi-3 in binary to the maximum possible length given a number of cits, and other stuff, worded with power cut rather than abort. It was met with (positive) criticism asking how one would determine valid answers. I realized that likely I could not, and removed the question. With this meticulously worded code-golf, I'm confident that I can check the program, or post a shorter tenacious one, for many languages. My only regret is that I should have made the goal a tad more sexy. – fgrieu Apr 26 '12 at 18:08
• Are you sure you want this to be code golf? It seems to me that the challenge is in writing such a program at all (and proving its correctness); once that's accomplished, golfing it becomes a fairly trivial exercise (and somewhat ill-defined, given that we're allowed to adapt the interface). Maybe just make it code-challenge instead? – Ilmari Karonen Apr 28 '12 at 14:54
• Another question: would proving the impossibility of non-trivial tenacious programs count as a solution? (I don't have such a proof yet, but I'm starting to think that may be the case.) – Ilmari Karonen Apr 28 '12 at 20:13
• @IlmariKaronen: Proof of impossibility would be king! I have posted a solution that may be valid. See for yourself. – fgrieu May 2 '12 at 19:59

While I don't have a solution nor a proof of impossibility, I figured I'd post my test harness for anyone wanting to play around with this, as I've pretty much given up at this point.

It's an implementation of the HAL modelling programs as a Haskell monad. It checks for tenacity by doing a breadth-first search over the possible sessions to check for sessions which either 1. have halted once without producing the correct output, or 2. have produced an output that is not a prefix of the desired one (this also catches programs producing infinite output).

{-# LANGUAGE GADTs #-}

module HAL where

import Data.List

import Data.Map (Map)
import qualified Data.Map as Map

import Data.Set (Set)
import qualified Data.Set as Set

newtype CitIndex = Cit Int
deriving (Eq, Ord, Show)

data CitState = Stable Int | Unstable
deriving (Eq, Ord, Show)

data Program a where
Return :: a -> Program a
Bind :: Program a -> (a -> Program b) -> Program b
Put :: Int -> Program ()
Read :: CitIndex -> Program Int
Write :: CitIndex -> Int -> Program ()
Log :: String -> Program ()
Halt :: Program ()

return = Return
(>>=) = Bind

data Session = Session
{ cits :: Cits
, output :: [Int]
, lastPut :: Int
, halted :: Bool
} deriving (Eq, Ord, Show)

data Event
| PutE Int
| WriteSuccessE CitIndex Int
| WriteAbortedE CitIndex Int
| LogE String
| HaltedE
deriving (Eq, Ord, Show)

type Log = [(Event, Cits)]

check :: Program () -> Int -> [Int] -> IO ()
check program n goal =
case tenacity (program >> Halt) goal of
Tenacious  -> putStrLn "The program is tenacious."
Invalid ss -> do
putStrLn "The program is invalid. Example sequence:"
forM_ (zip [1..] ss) $\(i, (log, s)) -> do ruler putStrLn$ "Run #" ++ show i ++ ", Initial state: " ++ formatState n s
ruler
mapM_ (putStrLn . formatEvent n) log
where ruler = putStrLn $replicate 78 '=' run :: Program a -> Session -> [(Maybe a, Log, Session)] run (Return x) s = [(Just x, [], s)] run (Bind x f) s = do (r1, l1, s1) <- run x s case r1 of Just y -> [(r2, l1 ++ l2, s2) | (r2, l2, s2) <- run (f y) s1] Nothing -> [(Nothing, l1, s1)] run (Put x) s = [(Just (), [(PutE x, cits s)], s')] where s' | lastPut s /= x = s { lastPut = x, output = output s ++ [x mod 2] } | otherwise = s run (Read cit) s = case lookupCit cit (cits s) of Stable x -> [(Just x, [(ReadE cit x, cits s)], s)] Unstable -> [(Just x, [(ReadE cit x, cits s)], s) | x <- [0, 1]] run (Write cit x) (s @ Session { cits = cits }) = [(Just (), [(WriteSuccessE cit x, completed)], s { cits = completed }), (Nothing, [(WriteAbortedE cit x, aborted )], s { cits = aborted })] where state = lookupCit cit cits completed = updateCit cit newState cits where newState = case (x, state) of (0, _) -> Stable 0 (1, Unstable) -> Unstable (1, Stable _) -> Stable 1 aborted = updateCit cit newState cits where newState = case (x, state) of (0, Stable 0) -> Stable 0 (0, _) -> Unstable (1, Stable 1) -> Stable 1 (1, _) -> Unstable run (Halt) s = [(Just (), [(HaltedE, cits s)], s { halted = True })] run (Log msg) s = [(Just (), [(LogE msg, cits s)], s)] newSession :: Session newSession = Session { cits = initialCits , output = [] , lastPut = 0 , halted = False } newtype Cits = Cits (Map CitIndex CitState) deriving (Eq, Ord, Show) initialCits = Cits (Map.empty) lookupCit :: CitIndex -> Cits -> CitState lookupCit cit (Cits m) = Map.findWithDefault (Stable 0) cit m updateCit :: CitIndex -> CitState -> Cits -> Cits updateCit index (Stable 0) (Cits m) = Cits$ Map.delete index m
updateCit index newState (Cits m) = Cits $Map.insert index newState m data Tenacity = Tenacious | Invalid [(Log, Session)] deriving (Eq, Ord, Show) tenacity :: Program () -> [Int] -> Tenacity tenacity program goal = bfs Set.empty [(newSession, [])] where bfs :: Set Session -> [(Session, [(Log, Session)])] -> Tenacity bfs visited [] = Tenacious bfs visited ((s, pred) : ss) | Set.member s visited = bfs visited ss | valid s = bfs (Set.insert s visited)$ ss ++ [(s', (l, s) : pred) | (_, l, s') <- run program s]
| otherwise = Invalid $reverse (([], s) : pred) valid :: Session -> Bool valid Session { output = output, halted = halted } | halted = output == goal | otherwise = output isPrefixOf goal formatState :: Int -> Session -> String formatState n s = "[cits: " ++ dumpCits n (cits s) ++ "] [output: " ++ dumpOutput s ++ "]" formatEvent :: Int -> (Event, Cits) -> String formatEvent n (event, cits) = pad (78 - n) text ++ dumpCits n cits where text = case event of ReadE (Cit i) x -> "read " ++ show x ++ " from cit #" ++ show i PutE x -> "put " ++ show x WriteSuccessE (Cit i) x -> "wrote " ++ show x ++ " to cit #" ++ show i WriteAbortedE (Cit i) x -> "aborted while writing " ++ show x ++ " to cit #" ++ show i LogE msg -> msg HaltedE -> "halted" dumpCits :: Int -> Cits -> String dumpCits n cits = concat [format$ lookupCit (Cit i) cits | i <- [0..n-1]]
where format (Stable i) = show i
format (Unstable) = "U"

dumpOutput :: Session -> String
dumpOutput s = concatMap show (output s) ++ " (" ++ show (lastPut s) ++ ")"

pad :: Int -> String -> String
pad n s = take n $s ++ repeat ' '  Here is the example program given by the OP converted to Haskell. import Control.Monad (when) import HAL -- 3 cits, goal is 01 main = check example 3 [0, 1] example = do c <- Read (Cit 2) d <- Read (Cit c) when (0 == c)$ do
Log "in first branch"
Write (Cit 2) 0
Write (Cit 1) 0
Write (Cit 1) (1 - d)
Write (Cit 2) 1
Write (Cit 0) 0
when (d == c) \$ do
Log "in second branch"
Put 2
Write (Cit 2) 0
Write (Cit 0) 1
Put 1


And here is the corresponding output, showing that the program is not tenacious.

The program is invalid. Example sequence:
==============================================================================
Run #1, Initial state: [cits: 000] [output:  (0)]
==============================================================================
read 0 from cit #2                                                         000
read 0 from cit #0                                                         000
in first branch                                                            000
wrote 0 to cit #2                                                          000
wrote 0 to cit #1                                                          000
wrote 1 to cit #1                                                          010
wrote 1 to cit #2                                                          011
wrote 0 to cit #0                                                          011
in second branch                                                           011
put 2                                                                      011
wrote 0 to cit #2                                                          010
wrote 1 to cit #0                                                          110
put 1                                                                      110
halted                                                                     110
==============================================================================
Run #2, Initial state: [cits: 110] [output: 01 (1)]
==============================================================================
read 0 from cit #2                                                         110
read 1 from cit #0                                                         110
in first branch                                                            110
wrote 0 to cit #2                                                          110
wrote 0 to cit #1                                                          100
wrote 0 to cit #1                                                          100
aborted while writing 1 to cit #2                                          10U
==============================================================================
Run #3, Initial state: [cits: 10U] [output: 01 (1)]
==============================================================================
read 1 from cit #2                                                         10U
read 0 from cit #1                                                         10U
wrote 0 to cit #0                                                          00U
aborted while writing 1 to cit #0                                          U0U
==============================================================================
Run #4, Initial state: [cits: U0U] [output: 01 (1)]
==============================================================================
read 0 from cit #2                                                         U0U
read 0 from cit #0                                                         U0U
in first branch                                                            U0U
wrote 0 to cit #2                                                          U00
wrote 0 to cit #1                                                          U00
wrote 1 to cit #1                                                          U10
wrote 1 to cit #2                                                          U11
wrote 0 to cit #0                                                          011
in second branch                                                           011
put 2                                                                      011
wrote 0 to cit #2                                                          010
wrote 1 to cit #0                                                          110
put 1                                                                      110
halted                                                                     110
==============================================================================
Run #5, Initial state: [cits: 110] [output: 0101 (1)]
==============================================================================


Unless someone can find a bug in this program, I think it checks and rejects every relevant two-cit program.

I argue that it suffices to consider programs which read all the cits and switch on a number formed by the set. Each branch of the switch will be a series of writes and puts. There's never any point putting the same number more than once in a branch, or putting the second output digit before the first one. (I'm morally certain that there's no point outputting the first digit other than at the start of a branch or the second digit other than at the end, but for now I'm avoiding that simplification).

Then each branch has a target set of cits it wants to set, and moves towards it by setting the bits it wants to be 0 as 0, and the bits it wants to be 1 as 0 then 1; these write operations can be ordered in various ways. There's no point setting a bit to 1 unless you've already set it to 0 in that run, or it's likely a nop.

It considers 13680577296 possible programs; it took a 4-core machine just under 7 hours to check them all without finding a single solution.

import java.util.*;

// State is encoded with two bits per cit and two bits for the output state.
//    ... [c_2=U][c_2=1/U][c_1=U][c_1=1/U][output_hi][output_lo]
// Output state must progress 0->1->2.
// Instruction (= program branch) is encoded with three or four bits per step.
//      The bottom two bits are the cit, or 0 for output/loop
//      If they're 0, the next two bits are 01 or 10 for output state, or 11 for halt.
//      Otherwise the next two bits are the value to write to the cit.
public class CitBruteForcer implements Runnable {

static final int[] TRANSITION_OK = new int[]{
// Index: write curr_hi curr_lo
0,  // write 0 to 0 => 0
0,  // write 0 to 1 => 0
0,  // write 0 to U => 0
-1, // invalid input
1,  // write 1 to 0 => 1
1,  // write 1 to 1 => 1
2,  // write 1 to U => U
-1  // invalid input
};
static final int[] TRANSITION_ABORT = new int[]{
// Index: write curr_hi curr_lo
0,  // write 0 to 0 => 0
2,  // write 0 to 1 => U
2,  // write 0 to U => U
-1, // invalid input
2,  // write 1 to 0 => U
1,  // write 1 to 1 => 1
2,  // write 1 to U => U
-1  // invalid input
};

private final int[] possibleInstructions;
private final int numCits, offset, step;
private long tested = 0;

private CitBruteForcer(int numCits, int[] possibleInstructions, int offset, int step)
{
this.numCits = numCits;
this.possibleInstructions = possibleInstructions;
this.offset = offset;
this.step = step;
}

public void run()
{
int numStates = 1 << numCits;
int n = possibleInstructions.length;
long limit = pow(n, numStates);

for (long i = offset; i < limit; i += step) {
// Decode as a base-n number.
int[] instructions = new int[numStates];
long tmp = i;
for (int j = 0; j < numStates; j++, tmp /= n) instructions[j] = possibleInstructions[(int)(tmp % n)];
Program p = new Program(numCits, instructions);
if (p.test()) System.out.println("Candidate: " + i);
tested++;
}
}

public static void main(String[] args) {
int numCits = 2;
int[] possibleInstructions = buildInstructions(numCits);

int numStates = 1 << numCits;
int n = possibleInstructions.length;
System.out.println(n + " possible instructions");
long limit = pow(n, numStates);

for (int i = 0; i < numThreads; i++) {
forcers[i] = new CitBruteForcer(numCits, possibleInstructions, i, numThreads);
}

int pc = 0;
while (pc < 100) {
// Every 10 secs is easily fast enough to update
try { Thread.sleep(10000); } catch (InterruptedException ie) {}

long tested = 0;
for (CitBruteForcer cbf : forcers) tested += cbf.tested; // May underestimate because the value may be stale
int completed = (int)(100 * tested / limit);
if (completed > pc) {
pc = completed;
System.out.println(pc + "% complete");
}
}
System.out.println(limit + " programs tested");
}

private static int[] buildInstructions(int numCits) {
int limit = (int)pow(3, numCits);
Set<Integer> instructions = new HashSet<Integer>();
for (int target = 0; target <= limit; target++) {
int toSetZero = 0, toSetOne = 0;
for (int i = 0, tmp = target; i < numCits; i++, tmp /= 3) {
if (tmp % 3 == 0) toSetZero |= 1 << i;
else if (tmp % 3 == 1) toSetOne |= 1 << i;
}
buildInstructions(0xc, toSetZero, toSetOne, false, false, instructions);
}
int[] rv = new int[instructions.size()];
Iterator<Integer> it = instructions.iterator();
for (int i = 0; i < rv.length; i++) rv[i] = it.next().intValue();
return rv;
}

private static void buildInstructions(int suffix, int toSetZero, int toSetOne, boolean emitted0, boolean emitted1, Set<Integer> instructions)
{
if (!emitted1) {
buildInstructions((suffix << 4) + 0x8, toSetZero, toSetOne, false, true, instructions);
}
if (!emitted0) {
buildInstructions((suffix << 4) + 0x4, toSetZero, toSetOne, true, true, instructions);
}
if (toSetZero == 0 && toSetOne == 0) {
return;
}

for (int i = 0; toSetZero >> i > 0; i++) {
if (((toSetZero >> i) & 1) == 1) buildInstructions((suffix << 3) + 0x0 + i+1, toSetZero & ~(1 << i), toSetOne, emitted0, emitted1, instructions);
}
for (int i = 0; toSetOne >> i > 0; i++) {
if (((toSetOne >> i) & 1) == 1) buildInstructions((suffix << 3) + 0x4 + i+1, toSetZero | (1 << i), toSetOne & ~(1 << i), emitted0, emitted1, instructions);
}
}

private static long pow(long n, int k) {
long rv = 1;
while (k-- > 0) rv *= n;
return rv;
}

static class Program {
private final int numCits;
private final int[] instructions;
private final Set<Integer> checked = new HashSet<Integer>();
private final Set<Integer> toCheck = new HashSet<Integer>();

Program(int numCits, int[] instructions) {
this.numCits = numCits;
this.instructions = (int[])instructions.clone();
}

boolean test() {
try {
while (!toCheck.isEmpty()) checkNext();
} catch (Exception ex) {
return false;
}

// Need each reachable state which hasn't emitted the full output to be able to reach one which has.
Set<Integer> reachable = new HashSet<Integer>(checked);
for (Integer reached : reachable) {
checked.clear();
toCheck.clear();
while (!toCheck.isEmpty()) checkNext();
boolean emitted = false;
for (Integer i : checked) {
if ((i.intValue() & 3) == 2) emitted = true;
}
if (!emitted) return false;
}

return true;
}

private void checkNext() {
Integer state = toCheck.iterator().next();
toCheck.remove(state);
run(state.intValue());
}

private void run(final int state) {
// Check which instructions apply
for (int i = 0; i < instructions.length; i++) {
boolean ok = true;
for (int j = 1; j <= numCits; j++) {
int cit = (state >> (2 * j)) & 3;
if (cit == 2 || cit == ((i >> (j-1)) & 1)) continue;
ok = false; break;
}
if (ok) run(state, instructions[i]);
}
}

private void run(int state, int instruction) {
while (true) {
int cit = instruction & 3;
if (cit == 0) {
int emit = (instruction >> 2) & 3;
if (emit == 3) break;
if (emit > (state & 3) + 1 || emit < (state & 3)) throw new IllegalStateException();
state = (state & ~3) | emit;
instruction >>= 4;
}
else {
int shift = 2 * cit;
int transitionIdx = (instruction & 4) + ((state >> shift) & 3);
int stateMasked = state & ~(3 << shift);
state = stateMasked | (TRANSITION_OK[transitionIdx] << shift);
instruction >>= 3;
}
// Could abort between instructions (although I'm not sure this is strictly necessary - this is "better" than the mid-instruction abort
consider(state);
}
// Halt or loop.
consider(state);
}

private void consider(int state) {
}
}
}

• If I use my assumption about placement of outputs, the number of 2-cit programs drops considerably and the checking time is less than a minute, but even with this assumption the number of 3-cit programs is more than 2^80, or a factor of about 2^47 more than the 2-cit programs checked in 7 hours. Not reasonably brute-forceable, in other words. – Peter Taylor May 4 '12 at 16:58

This is was my best attempt at answering my own question. I am uncertain that it meets requirement 3, and am open to refutation. It is not tenacious :-(

/*  1 */    #include "hal.h"
/*  2 */    main(){
/*  3 */        unsigned c = r(2);  // get cit 2 into c
/*  4 */        unsigned d = r(c);  // get cit c into d
/*  5 */    // here if d==c then we have not output 1 yet
/*  6 */    //              else we have     output 0
/*  7 */        if (0==c)
/*  8 */            w( 2, 0 ),      // cit 2 to 0
/*  9 */            w( 1, 0 ),      // cit 1 to 0
/* 10 */            w( 1,!d ),      // cit 1 to complement of d
/* 11 */            w( 2, 1 );      // cit 2 to 1
/* 12 */        w( 0, 0 );          // cit 0 to 0
/* 13 */        if (d==c)
/* 14 */            p( 2 ),         // put 2, first one outputs 0
/* 15 */            w( 2, 0 );      // cit 2 to 0
/* 16 */        w( 0, 1 );          // cit 0 to 1
/* 17 */        p( 1 );             // put 1, first one outputs 1
/* 16 */    }                       // halt

• My test program says that's not tenacious: 1. Run program to completion. Output: 01, Cits: 110. 2. Abort during #15. Cits: 10U. 3. Read c = 1, abort during #12. Cits: U0U. 4. Read c = 0, d = 0 and the program will print 01 again. – hammar May 2 '12 at 20:38
• Sorry, the first abort should be at line #11, not #15. – hammar May 2 '12 at 21:20