% Logik og sprog, Modul 2, datalogi RUC      Henning Christiansen
%
% 
% Turing-maskiner i Prolog;
% kapitel 10 i "Sprog og abstrakte maskiner"
%
% (c) 2000, Henning Christiansen

% NB: Denne fil definerer en fortolker for Turing maskiner, der er
% repr¾senteret ved pr¾dikater t/5, start/1 og slut/1.
%
% Se eksempler i filerne TuringCount.txt og TuringMultiply.txt
% som skal consultes efter n¾rv¾rende fil.

% Et bŒnd er repr¾senteret ved et struktur
%
%      tape(venstre, fokus, h¿jre)
%
% hvor fokus angiver tegnet under l¾sehovedet,
% h¿jre og venstre er lister svarende til det, som
% de respektive dele af bŒndet pŒ hver side af
% l¾sehovedet.
%
% Eksempel: Det f¿lgende bŒnd,
%
% --------------------------------------------
%      | a | b | c | d | e | f |
% --------------------------------------------
%                /\
%
%  er repr¾senteret ved:
%
%      tape([b,a|'...'] c, [d,e,f|'...']).
%
% Dvs. bŒndet er sŒ at sige "foldet", hvilket g¿r
% det nemmere at flytte l¾sehovedet i begge
% retninger.
%
% BŒndender bestŒende af uendeligt mange
% blanktegn er repr¾senteret ved atomet '...';
% blanktegn, som ikke er del af bŒndende er repr¾senteret
% ved atomet ' '.
%
% Transitionsreglerne skal gives i form af regler, om et
% pr¾dikat, t,
%
%   t( aktuel-tilst., aktuel-tegn, ny-tilst., nyt-tegn, retning )
%
% Tilstandende angives ved Prolog-atomer, tegnene ligesŒ.
% Retninger anviges ved symbolerne <-- og --> til at angive
% retningerne venstre og h¿jre, --- stŒr for, at
% l¾se/skrivehovedet ikke flyttes

% Start-og sluttilstande skal v¾re bestemt ved fakta
% start(tilstand) og slut(tilstand) (evt. flere sluttilstande).
 

% At k¿re maskinen:
%
%   k¿r(start-bŒnd, slutbŒnd).
%
% Eksemplet 2 x 2 k¿res som f¿lger:
%
%   koer( tape('...', 1,[1,x,1,1|'...']), BaandSlut)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

koer( StartBaand, Slutbaand):-
    start(Q),
    koer( StartBaand, Q, Slutbaand, _).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% koer( bŒnd-f¿r, tilstand-f¿r, bŒnd-efter, tilstand-efter)

koer( Baand, Q, Baand, Q):-
    slut(Q),!.

koer( BaandFoer, Qfoer, BaandStop, QStop):-
    laes(BaandFoer, AktueltTegn),
    t(Qfoer, AktueltTegn, Qefter, NytTegn, Retning),
    skriv( NytTegn, BaandFoer, BaandMellem ),
    ryk(Retning, BaandMellem, BaandEfter),
    koer( BaandEfter, Qefter, BaandStop, QStop).


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%  BŒndoperationer

% laes( <bŒnd>, <aktuelt-tegn> )

laes( tape(_, T, _), T).

% skriv( <nyt-tegn>, <bŒnd-f¿r>, <bŒnd-efter> )

skriv( T, tape(V_er, _, H_er), tape(V_er, T, H_er)).

% liste( <hovede>, <hale> ,<liste> )

liste( ' ', '...', '...'):- !.

liste( Ho, Ha, [Ho | Ha]).

% ryk( <retning>, <bŒnd-f¿r>, <bŒnd-efter> )

ryk(---, B, B).

ryk(-->, tape( V_er1, F1, H_er1), tape( V_er2, F2, H_er2) ):-
    liste(F1, V_er1, V_er2),
    liste(F2, H_er2, H_er1).

ryk(<--, tape( V_er1, F1, H_er1), tape( V_er2, F2, H_er2) ):-
    liste(F2, V_er2, V_er1),
    liste(F1, H_er1, H_er2).