1 #maxint=20.
   2 
   3 %------------- Command line options ---------------
   4 % -nofdcheck -filter=tape
   5 %--------------------------------------------------
   6 
   7 %%%%%%%%%%%%%%%%%%%
   8 % initial situation
   9 
  10 position(0,0).
  11 
  12 state(s0,0).
  13 
  14 % first example: it halts!
  15 tape(0,i,0). tape(1,1,0). tape(2,1,0). tape(3,0,0).
  16 tape(4,1,0). tape(5,1,0).
  17 lastUsedPos(5,0).
  18 
  19 % second example: it does not halt!
  20 %tape(0,i,0). tape(1,1,0). tape(2,1,0).
  21 %lastUsedPos(2,0).
  22 
  23 
  24 %%%%%%%%%%%%%%%%%%%%%
  25 % transition function
  26 
  27 % first example: it halts!
  28 delta(s0,i,s0,i,right). delta(s0,0,s0,0,right). delta(s0,1,s0,1,right). delta(s0,blank,s1,blank,left).
  29 delta(s1,i,f,i,right). delta(s1,0,f,1,nomove). delta(s1,1,s1,0,left).
  30 
  31 % second example: it does not halt!
  32 %delta(s0,i,s0,i,right). delta(s0,0,s1,0,left). delta(s0,1,s0,1,right). delta(s0,blank,s0,1,right). 
  33 %delta(s1,0,f,0,nomove). delta(s1,1,f,1,nomove). delta(s1,i,f,i,nomove).
  34 
  35 
  36 %%%%%%%%%%%%%%%%%%%%%%
  37 % position description
  38 
  39 position(#prec(P),#succ(T)) :- position(P,T), state(St,T), tape(P,Sym,T),
  40                                delta(St,Sym,_,_,left), P!=0.
  41 position(#succ(P),#succ(T)) :- position(P,T), state(St,T), tape(P,Sym,T),
  42                                delta(St,Sym,_,_,right).
  43 position(P,#succ(T))        :- position(P,T), state(St,T), tape(P,Sym,T),
  44                                delta(St,Sym,_,_,nomove).
  45 
  46 lastUsedPos(L,#succ(T)) :- lastUsedPos(L,T), position(P,T), P<=L.
  47 lastUsedPos(P,#succ(T)) :- lastUsedPos(L,T), position(P,T), P>L.
  48 
  49 
  50 %%%%%%%%%%%%%%%%%%%%%%
  51 % state description
  52 
  53 state(St1,#succ(T)) :- position(P,T), state(St,T), tape(P,Sym,T), 
  54                        delta(St,Sym,St1,_,_).
  55 
  56 
  57 %%%%%%%%%%%%%%%%%%%%%%
  58 % tape description
  59 
  60 tape(P,Sym1,#succ(T)) :- position(P,T), state(St,T), tape(P,Sym,T),
  61                          delta(St,Sym,_,Sym1,_).
  62 tape(P,Sym,#succ(T))  :- position(P1,T), tape(P,Sym,T), P!=P1.
  63 tape(P,blank,T)       :- position(P,T), lastUsedPos(L,T), P>L.