Algorithm design for time travelers

In sci-fi, there are broadly two types of time travel depending on whether timelines are mutable or immutable. If they're mutable, then you can go back in time and genuinely alter the past, resulting in dangerous or heroic results for the future. (Think Bradbury's A Sound of Thunder, in which a timetraveler's misstep in the Cretaceous period alters the present day). If they're immutable, then although you can go back in time, your actions cannot change the future because they're already intrinsic to events as they happened. (Think Terminator, in which a timetraveler who attempts to prevent John Connor from being born inadvertently causes his parents to meet.)

Immutable timelines are computationally interesting. They involve stable time loops—self-consistent and self-contained sequences of events in which all the time travel is completely consistent with events as they turn out. In a stable time loop, time travel is always idempotent. In order to find a stable time loop, it seems like you must do computational work—a kind of search over all the ways things could have shaken out, in order to find a sequence of events that is self-consistent and self-contained.

Presumably in a universe with stable time loops, the universe itself computes the stable sequence of events. It's a kind of equilibrium solution, a fixed point or minimum (like a soap bubble surface). If you are a time traveler in a universe with only stable time loops, you can extract computational work out of the universe's insistence on stable time loops. Here's an example algorithm that uses stable time loops to crack a password:

1. Suppose for simplicity that the password is either A or B.
2. Commit to the following algorithm:
3. If a piece of paper has materialized in your pocket, read off the letter written on it. Type it into the computer to see if it unlocks.
   1. If it does indeed unlock, send the piece of paper back in time so that it materializes in your pocket.
   2. Otherwise, scribble it out and send it back in time so that the scribble materializes in your pocket.
4. If no piece of paper has materialized in your pocket, find a piece of paper.
5. Choose one of the two letters A or B to write down on it.
6. Send the piece of paper back in time so that it materializes in your pocket.

The branches of this computation create a stable loop only in the case that a piece of paper with the correct answer (in your handwriting) mysteriously materializes in your pocket at the start of the algorithm, you confirm the password is correct, then complete the time loop by sending the paper back in time into your pocket. Hence if you can time-travel and only stable time loops are possible, you can use this algorithm to extract a password.

There's more to say about the detailed model of time travel and nondeterminism I'm working with here, but this example gives the flavor. (For more details, see the Appendix.)

Wouldn't it be cool to actually program like this? Turns out you can.

The Clojure code in this section enables you to write time-travel-enabled algorithms; i.e. algorithms that nondeterministically search through possible outcomes, returning only those that result in stable time loops. Through clever design, you can ensure that only the correct answer will result in a stable time loop.

Here, for illustration, is how you write that password-cracking algorithm:

  ;;; PASSWORD SOLVER. If you have a time-traveled paper in your pocket,
  ;;; read it and enter the answer into the computer. If it works, send
  ;;; it back in time to where you first found it in your pocket
  ;;; (otherwise autofail).  If you have no time-traveled paper, pick
  ;;; one of the possible passwords and send it back in time.

  ((fn breaker-fn [u]
     (let [possible-passwords [:A :B :C :D]]
       (if (some? (:paper-mark u))
         (when (= (:true-password u) (:paper-mark u))
           (close-loop breaker-fn u) )

         (keep-stable-loops
          (for [mark possible-passwords]
            (close-loop
             breaker-fn u {:paper-mark mark}))))))

   {:true-password :B})

;; result=> ({:true-password :B, :paper-mark :B})

We can note a few things:

1. A time-travel-enabled algorithm is a function that takes in a "state of the universe" u and yields a stable list of such universe states (possibly empty, if no such loop exists.)
2. Universes are represented as hash-maps of their properties. For example, the input universe is a world in which the true password is :B.
3. The time travel loop begins when the function is called, and ends whenever close-loop is called, transmitting some updated information into the past. A stable time loop occurs whenever the call to close-loop has no effect on the universe—it's a fixed point.
4. Note that when the function is called, it finds and yields the single stable time loop — an altered version of the input universe in which a piece of paper has materialized with the correct password written on it (in this example, :B).

This algorithm relies on a few subroutines for consolidating and comparing world-states:

(ns ai.logical.timeloop)

;;;;;;;;;;;;;;;;; HELPER FUNCTIONS

(defn other-one
  "Given an object and a list of two or more items, returns an item that
  is different from the object."
  [x [a b]]
  (if (= x a) b a))

(defn unify [to from]
  "Augment the to-map with the entries of from-map, unless the maps
   conflict, in which case return nil.

   (Maps conflict if to-map and from-map have different values at the
   same key, and to-map isn't null there.)"

  (when (every? #(= (get from %)
                    (get to % (get from %)))
                (keys from))
    (into to from)))

;;;;;;;;;;;;;;;;; TIME TRAVEL UTILITIES


(defn resolve-branches
  "Given a tree (nested list) of self-consistent world
  states (hash-maps), return a flattened list of self-consistent world
  states, removing duplicates and nil elements."
  [& branches]
  ((fn flatten-tree [x]
     ;; leaf: world state
     (if (map? x) 
       (list x)

       ;; branch: list of trees
       (distinct
        (remove nil?
                (mapcat flatten-tree x)))))
   branches))

(def keep-stable-loops
  "Flatten a (possibly nested) list of stable world-states into a single
  flat list, removing all duplicates and nil elements.

  Alias of resolve-branches."
  resolve-branches)

(defn close-loop
  "Close the temporal loop by transmitting an update to the world state
  at the onset of the temporal loop. (Default update is nil, no change.)

  If the update is compatible and has no effect, the world state is
  stable---return it. If the update is compatible and changes the
  world state, reiterate the time loop --- call recur-fn on the updated
  world state. If the update is incompatible, the loop is unstable ---
  return nil."

  ([recur-fn world-state updated-info]
   (when-let [world-state* (unify world-state updated-info)]
     (do ;;(println :compatible world-state pattern world-state*)
       (if (= world-state* world-state) world-state
           (recur-fn world-state*)))))
  ([recur-fn world-state]
   (close-loop recur-fn world-state nil)))

Here are some more examples of time-travel-enabled algorithms:

    ;;;;; PARADOX FUNCTION. If you have a timetraveled paper in your
    ;;;;; pocket with A or B written on it, create a ?new piece of paper
    ;;;;; with the other symbol written on it and send it back in time.
    ((fn paradox-fn [u]
       (let [possible-passwords [:A :B]]

         (if (some? (:paper-mark u))
           (close-loop paradox-fn u
                       ;; this line creates the paradox vvv
                       {:paper-mark
                        (other-one (:paper-mark u) possible-passwords)})
           (keep-stable-loops
            (for [mark possible-passwords]
              (close-loop paradox-fn u {:paper-mark mark}))))))

     {})

  ;; => Returns (); no stable time loops exist.



    ;;;;; NON-PARADOX FUNCTION. Near-miss modification of the above. If
    ;;;;; you have a time-traveled piece of paper in your pocket, send it
    ;;;;; back in time as-is, closing the time loop. Otherwise, write down
    ;;;;; either :A or :B on a piece of paper and send it back.
    ;;;;;
    ;;;;; There are, of course, two stable time loops here.

    ((fn non-paradox-fn [u]
       (let [possible-passwords [:A :B]]

         (if (some? (:paper-mark u))
           (close-loop non-paradox-fn u)

           (keep-stable-loops
            (for [mark possible-passwords]
              (close-loop non-paradox-fn u {:paper-mark mark}))))))

     {})

;; => Returns ({:paper-mark :A}, {:paper-mark :B}); two stable time loops exist.




  ;;; NASH EQUILIBRIUM. Stable time loops can find Nash equilibria.
  ;;  Players write down their choice of action on a public ledger, then
  ;;; send the ledger back in time. At the start of the time loop, each
  ;;; player gets to review the public ledger and, if they want, to
  ;;; alter their own entry. If a person alters the ledger, they send
  ;;; the ledger back in time immediately. Otherwise, they hand it to
  ;;; the next person for review. After everyone accepts the ledger
  ;;; without alteration, the ledger is sent back one last time. The
  ;;; only stable time loops are Nash equilibria.

  ;; The following example showcases the prisoner's dilemma.

  ((fn nash-fn [u]
     (let [actions [:cooperate :defect]
           payout-matrix
           {[:cooperate :cooperate] [3 3],
            [:cooperate :defect]    [0 5],
            [:defect :cooperate]    [5 0],
            [:defect :defect]       [1 1]}]

       (cond (nil? (:choice-1 u))
             (keep-stable-loops
              (for [act actions]
                (close-loop nash-fn u
                            {:choice-1 act})))

             (nil? (:choice-2 u))
             (keep-stable-loops
              (for [act actions]
                (close-loop nash-fn u
                            {:choice-2 act})))


             :default
             (let [preferred-act-1 (first (filter
                                           #(> (first (payout-matrix [% (:choice-2 u)]))
                                               (first (payout-matrix [(:choice-1 u) (:choice-2 u)])))
                                           actions))
                   preferred-act-2 (first (filter
                                           #(> (second (payout-matrix [(:choice-1 u) %]))
                                               (second (payout-matrix [(:choice-1 u) (:choice-2 u)])))
                                           actions))]
               (cond (some? preferred-act-1) ;; PLAYER 1 PREFERS A DIFFERENT MOVE, GIVEN PLAYER 2's.
                     (keep-stable-loops (close-loop nash-fn u {:choice-1 preferred-act-1}))

                     (some? preferred-act-2) ;; PLAYER 2 PREFERS A DIFFERENT MOVE, GIVEN PLAYER 1's.
                     (keep-stable-loops (close-loop nash-fn u {:choice-2 preferred-act-2}))

                     :default ;; NEITHER PLAYER COULD UNILATERALLY IMPROVE THEIR PAYOUT
                     (keep-stable-loops (close-loop nash-fn u)))))))
   {})
    ;; => ({:choice-1 :defect, :choice-2 :defect})


    ;;;;; KNOCKER FUNCTION. A naive attempt to break a password using
    ;;;;; iteration instead of branching will fail to resolve into a
    ;;;;; stable time loop: Suppose the password is numeric, between
    ;;;;; 0-9. If you have a time-traveled paper, read off the number and
    ;;;;; enter it into the computer. If it works, send it back in time.
    ;;;;; If it doesn't, create a ?brand-new piece of paper with the next
    ;;;;; number on it and send it back in time instead. But --- then who
    ;;;;; sent your original paper back in time? And why didn't you
    ;;;;; receive the new paper in your original timeline?  A stable time
    ;;;;; manipulation can only set "what's on the paper" once and for
    ;;;;; all, and so this overwrite-and-rewind approach can't work. You
    ;;;;; need multiple notes instead (see next variation).

    ((fn knocker-fn [u]
       (if (some? (:paper-mark u))
           (if (= (:true-password u) (:paper-mark u))
             (close-loop knocker-fn u)
             (close-loop knocker-fn
                         (dissoc u :paper-mark) ;;; <- nonstandard mutation. in stable-loop-compliant algorithms, always ought to be just u itself.
                         (assoc u :paper-mark (inc (:paper-mark u)))
                         ))

           (close-loop knocker-fn u {:paper-mark 0})))

     {:true-password 8})

    ;;;;; FIXED KNOCKER FUNCTION. You are allowed to send multiple
    ;;;;; pieces of paper back in time, however. Here, I create multiple
    ;;;;; predicates, one for each slip of paper and its contents.

    ((fn multiknock-fn [u]
       (let [ordered-answers ["A" "B" "C" "D"] ;; four possible marks
             mark-attrs (for [m ordered-answers] (keyword (str "mark-" m))) ;; the universe-checking predicates are called :mark-A, :mark-B, etc.

             ;; This map sends each attribute to the one after it in the list
             next-mark (zipmap mark-attrs (rest mark-attrs))

             ;; You're supposed to write :A on the :mark-A paper, etc.
             what-to-write-on (comp keyword str last str)     
             ]

         (if-let [latest-mark ;; If you have /any/ slips of paper, look at
                              ;; the most recent one.
                  (first (filter #(% u) (reverse mark-attrs)))]
           (if (= (:true-password u) (latest-mark u)) ;; check if it's the true password
             (close-loop multiknock-fn u {:circled-answer (latest-mark u)})
             ;; if it's correct, circle it and send it back in time.
             ;; (circling cute and convenient but not necessary; could
             ;; just send back papers as-is.)

             ;; if it's incorrect, create a new slip of paper with the
             ;; next candidate answer on it and send it back with /all/
             ;; the other slips of paper.
             (close-loop multiknock-fn u {(next-mark latest-mark)
                                          (what-to-write-on (next-mark latest-mark))}))

           ;; If you have no slips of paper, make one with the first
           ;; candidate answer on it and send it back in time.
           (close-loop multiknock-fn u {(first mark-attrs)
                                        (what-to-write-on (first mark-attrs))}))))
     {:true-password :C})



    ;;;; NESTED TIME LOOPS.

    ;;;; Each lamba function is a temporal anchor point. If you are
    ;;;; allowed to instantiate /nested/ temporal anchor points, you can
    ;;;; time travel back to a point other than the beginning of the main
    ;;;; function.

    ;;;; Here, we can use nested time travel to perform the knocking
    ;;;; routine to find the password, but without multiple pieces of
    ;;;; paper cluttering the true timeline.


    ((fn knock-anchor-outer [u]
       (if (some? (:marked-paper u))
         (when (= (:true-password u) (:marked-paper u))
           (close-loop knock-anchor-outer u))

         ((fn knock-anchor-inner [v]
            (let [ordered-answers ["A" "B" "C" "D"]
                  mark-attrs (for [m ordered-answers] (keyword (str "mark-" m)))
                  next-mark (zipmap mark-attrs (rest mark-attrs))
                  next-mark (assoc next-mark :mark-D :mark-X) ;; special symbol X indicates failure
                  what-to-write-on (comp keyword str last str)]

              (if-let [latest-mark
                       (first (filter #(% v) (reverse mark-attrs)))]
                (if (= (:true-password v) (latest-mark v))
                  (close-loop knock-anchor-outer u ;;<< CLOSE /OUTER/ LOOP!
                              {:marked-paper (latest-mark v)}) ;; send back single piece of marked paper to the outermost temporal anchor.

                  (close-loop knock-anchor-inner v
                              {(next-mark latest-mark)
                               (what-to-write-on (next-mark latest-mark))}))

                (close-loop knock-anchor-inner v
                            {(first mark-attrs)
                             (what-to-write-on (first mark-attrs))}))))
          u)))
     {:true-password :C})

Our model of time travel works as follows:

1. Nondeterminism exists. In a deterministic universe, you don't have any branching outcomes and hence the universe doesn't have to search branches for a stable timeline. If we're going to have stable time loops, we need nondeterministic branching.

   The source of nondeterminism could be microscopic (e.g. quantum probabilities, nuclear decay) or macroscopic (e.g. a person "freely choosing" to write down A or B, dice rolls, random accidents of nature) — the model isn't specific about what kind of nondeterminism there is.

   The nondeterminism in this setup is similar to the amb operator defined in the SICP book.

2. You initiate a time loop by committing to an algorithm. By commiting to a specific algorithm, you are committing to a definite set of possible outcomes. Specifying that set of possibilities is what makes the search space well-defined.

   For example, you commit to an algorithm which says "If a piece of paper is in my pocket, I'll read it and send it back in time. Otherwise, I'll go get a piece of paper and write A or B on it, then send that back in time." This algorithm limits the set of things that can materialize from the future to a piece of paper with A or B written on it.

   Without such an algorithm commitment, you run into one of the nasty issues with time travel: technically, it is self-consistent for anything whatsoever to materialize out of nowhere and burden you with shipping it back into the past to finish its time loop. A strange obelisk appears in your backyard, covered in writing of different languages? You lug it around until you can send it back to the exact moment it materialized. Now you have this strangely sophisticated object that has no history, no authors, or anything; it just came from nowhere and goes nowhere.

   On the other hand, when you've committed to a specific algorithm, you've bound the universe of possibilities. (Compare the analogous problem with unbound variables in logic programming.)

3. There are nonconservative variants of this universe. The kind of time travel we're using violates conservation of matter/energy. After all, sending a note into the past suddenly increases the amount of matter in the past by one sheet of paper. If the note is part of a stable timeline, the graph of "total energy in the universe" jumps up when the note's time loop begins and jumps back down to baseline when it ends.

   So it's useful to envision a sheaf of variants of the current universe which have various time-traveled objects appended to it—notes, obelisks, anything. Entering into a time loop means the universe searches for one of these variants that has a self-consistent amount of stuff in it throughout the loop. For example, a note that materializes at the start of the loop and gets sent back, untouched, at the end of the loop.

4. You send predicates back into the past. The time loop ends when you call the time travel function to send information/matter back into the past. Concretely, we usually think of this as a physical object we want to send back in time, introducing it where it wasn't before.

   A more general way to think about it is as taking a predicate as an argument; an invocation of time travel requests that the universe at the beginning of the time loop satisfy that predicate. The predicate might be "__ contains the note I've just written", for example, or something more elaborate.

   In this view, the job of the universe's stable-time-loop finder is to see if there's a variant of the universe which satisfies this required predicate at the start of the time loop and which ends up in a computational branch where the final act of time travel sets up that property in the first place. This is a stable time loop because the act of time travel is idempotent.

   Time travel therefore consists of transmitting a specified change to the world from the end of the time loop to its beginning. If that change is contradictory (you can, for example, attempt to create Russell's paradox by sending back a different message from the one that materialized in your pocket), then the loop is inherently unstable. If it's congruent, then the loop is stable.

Computationally, this time travel model is implemented as follows:

1. Universe state as hash map The state of the universe is represented by a hash-map of its relevant properties and values. For example, if the true password to the computer is :A, and you have a mysterious paper with :B written on it, you might represent your universe as {:true-password :A, :paper-mark :B}.

2. Lexically-scoped time loops. Lambda functions create time loops. The time loop begins at the start of the function. The function's name can be used as a name for that initial moment in time. Time loops can be nested, neatly, through recursive calls to other functions.

   Time loops can also be nested, less neatly, through co-recursive calls. This corresponds to traveling between multiple overlapping temporal loops, or time travel involving multiple agents, and I haven't thought much about the complexities yet.

3. Close-loop recurs to the beginning of the loop. Like a return statement, every time-control-enabled function ends with a call to close-loop, a subroutine which takes as input (1) the input universe, (2) the start of the most recent time loop (i.e. the name of the innermost time-travel function), and (3) a hash-map representing properties you want to transmit to the start of the time loop and hence (when the loop is stable) which you want to hold throughout the entire time loop.

   The close-loop function works as follows: it first tests if the universe is compatible with the newly-required properties. The best case is if the universe already has all the required properties—then it represents a stable time loop with idempotent timetravel, so the universe can be returned directly. The next best case is if the universe doesn't have that property set; for example, if you want to send a note back in time and the note doesn't already exist at the start of your timeline. In that case, close-loop updates the universe and re-starts the timeloop by making a recursive call.

   The failure case is if the new properties contradict the existing universe; for example, if you found a timetraveled paper with the letter A on it, but you decide to send back a different paper with B written on it. Such an action cannot create a stable time loop, and so close-loop will return nil in this case.

4. Keep-stable-loops returns a list of equilibrium world states. The function close=loop returns a nested list of world-states belonging to stable timelines. The function keep-stable-loops flattens the list, removes duplicates, and removes nil elements.

   A nil world-state represents an unstable timeline, such as a Russell's paradox: if a piece of paper materializes in your pocket, take it out, write something else on a piece of paper and send it back in time. These actions cannot be part of a stable time loop, and so close-loop will return a null result.

5. Time travel is tail recursive. The time loop ends when you call the time travel function close-loop. The argument to a time travel invocation is a requested change to the state of the world. Concretely, we usually think of this as a physical object we want to send back in time, introducing it where it wasn't before. In terms of the hash-map representation, the requested change is simply a predicate that you wish for the universe to have at the start of the time loop.

   Time travel therefore consists of transmitting a specified change to the world from the end of the time loop to its beginning. If that change is contradictory (you can, for example, attempt to create Russell's paradox by sending back a different message from the one that materialized in your pocket), then the loop is inherently unstable. If it's congruent, then the loop is stable.

6. Stable time loops are equilibria. You can think of stable time loops as fixed points of these time-travel-enabled functions, in which case the universe's stable-loop-hunting function is a kind of fixed-point combinator.

   Incidentally, a kind of mundane stable time loop occurs in our universe with spontaneous particle creation and anihilation.

   I imagine a general rule of the form "If P and Q are conjugate variables, then 'Q-travel' (an instantaneous change in Q) violates 'conservation of P'." For example, here P is energy and Q is time, and time travel causes strange objects to materialize and persist throughout the duration of the time loop, violating conservation of energy.

7. Sometimes there are no stable time loops. The function will return the empty list. This is analogous to the result from the story HPMOR in which a mysterious scolding note appears, saying DO NOT MESS WITH TIME.

   In real life, the universe might resolve a fixed-point-free timeline via a breakdown in the time travel invocation itself: when it comes time to invoke time travel to close the loop as specified in your algorithm, the invocation simply fizzles and does nothing. A timeline in which no time travel occurs is generally always stable.

8. Time travel can find Nash equilibria. Earlier, I called stable time loops a kind of equilibrium solution. In fact, you can use time travel to form a Nash equilibrium as follows. A group of players begin a shared time loop that any one of them can revert.

   If a public whiteboard hasn't materialized yet, they acquire one; each person marks it with their chosen action, then the whiteboard is sent back in time for evaluation.

   If the public whiteboard has materialized, check to make sure you're satisfied with your choice given everyone else's choice. If not, scratch out your choice and send the modified whiteboard back in time. The only stable timeline is one in which the choices on the whiteboard form a Nash equilibrium.

9. Next steps: So far, I haven't accounted for random acts of nature (which might intervene and scupper the algorithm). I haven't dealt with time travel involving multiple interacting agents — I'm exploring a relatively simple kind of time travel, the kind that occurs relative to a definite origin point and definite ending point.

   This is, in a precise sense, tail-recursive time travel. You would need co-routines for that other stuff.

   I have one example above demonstrating nested time travel, i.e. time travel initiated within the scope of another time loop. It does work.

P.S. If you like thinking about this sort of thing, you might like my sci-fi short story Valley of the Timeflowers.