# SPARQL UPDATE Turing machine. Repeat query until a halting state is reached (the query will do nothing then)
# The tape is represented by a string literal and the symbols are "0" and "1"
# See http://www.brunni.de/sparql_turing_machine_example.txt for an example

WITH <http://turingmachine>

DELETE
{
 ?tm <http://state> ?oldstate.
 ?tm <http://tape> ?oldtape.
 ?tm <http://position> ?oldposition.
}

INSERT
{
 ?tm <http://state> ?newstate.
 ?tm <http://tape> ?newtape.
 ?tm <http://position> ?newposition.
}

WHERE
{
 ?tm <http://state> ?oldstate.
 ?tm <http://tape> ?oldtape.
 ?tm <http://position> ?oldposition.
 # If those are not there, ?oldstate is a halting state -> query does nothing
 ?oldstate <http://state0> ?state0.
 ?oldstate <http://state1> ?state1.

 # 0 at tape position
 OPTIONAL {
  select
  (CONCAT(SUBSTR(?oldtape,1,?oldposition-1),
         ?output0,
         SUBSTR(?oldtape,?oldposition+1)) as ?newtape)
  (?oldposition + ?movement0 as ?newposition)
  (?state0 as ?newstate)
  WHERE {
   ?tm <http://state> ?oldstate.
   ?tm <http://tape> ?oldtape.
   ?tm <http://position> ?oldposition.
   ?oldstate <http://output0> ?output0.
   ?oldstate <http://movement0> ?movement0.
   ?oldstate <http://state0> ?state0.
   FILTER(SUBSTR(?oldtape,?oldposition,1)="0")
  }
 }
 # 1 at tape position
 OPTIONAL {
  select
  (CONCAT(SUBSTR(?oldtape,1,?oldposition-1),
         ?output1,
         SUBSTR(?oldtape,?oldposition+1)) as ?newtape)
  (?oldposition + ?movement1 as ?newposition)
  (?state1 as ?newstate)
  WHERE {
   ?tm <http://state> ?oldstate.
   ?tm <http://tape> ?oldtape.
   ?tm <http://position> ?oldposition.
   ?oldstate <http://output1> ?output1.
   ?oldstate <http://movement1> ?movement1.
   ?oldstate <http://state1> ?state1.
   FILTER(SUBSTR(?oldtape,?oldposition,1)="1")
  }
 }
 # extend tape to the left
 OPTIONAL {
  select
  (CONCAT(?output0,?oldtape) as ?newtape)
  (?oldposition + ?movement0 as ?newposition)
  (?state0 as ?newstate)
  WHERE {
   ?tm <http://state> ?oldstate.
   ?tm <http://tape> ?oldtape.
   ?tm <http://position> ?oldposition.
   ?oldstate <http://output0> ?output0.
   ?oldstate <http://movement0> ?movement0.
   ?oldstate <http://state0> ?state0.
   FILTER(?oldposition=0)
  }
 }
 # extend tape to the right
 OPTIONAL {
  select
  (CONCAT(?oldtape,?output0) as ?newtape)
  (?oldposition + ?movement0 as ?newposition)
  (?state0 as ?newstate)
  WHERE {
   ?tm <http://state> ?oldstate.
   ?tm <http://tape> ?oldtape.
   ?tm <http://position> ?oldposition.
   ?oldstate <http://output0> ?output0.
   ?oldstate <http://movement0> ?movement0.
   ?oldstate <http://state0> ?state0.
   FILTER(?oldposition=strlen(?oldtape)+1)
  }
 }

}