Simulator Mesin Turing

Mesin TuringProgram ini bertujuan menirukan cara kerja mesin turing (lihat: Wikipedia). Mesin turing dianggap sebagai simulasi logika dari algoritma komputer, meskipun faktanya tidak ada komputer yang dirancang berdasarkan mesin turing. Program ini dibuat saat pelajaran Teori Automata tahun 1997, sesuai kapasitas pemahaman di saat itu. Program dibuat cukup singkat dan luwes dengan seperangkat aturan dalam sebuah file.

Nostalgia ini mengingat pula dosen saat itu, yaitu Teddy Mantoro (lihat: USBI). Salah satu dosen yang paling diingat karena sangat logis dalam menjelaskan. Terbukti, hingga sekarang sudah ratusan paper dibuat (tentu saja, karya bersama dosen dan mahasiswa) dan mengajar di berbagai universitas, termasuk di Malaysia. Ternyata pula salah satu rekan kerja di Kominfo, yaitu Aries Kusdaryono, belum lama ini membuat jurnal bersama dosen tersebut. Dunia ternyata tidak lebar.

Kunci dari berfungsinya program adalah seperangkat aturan yang terdapat dalam file RUL.DAT. Disertakan di file tersebut empat operasi yaitu tambah, kurang, kali, dan bagi. Dapat dibayangkan, ke-empat operasi tersebut dihasilkan dengan menggeser-geser ‘head’ pada gelondongan ‘tape’. Jangan tanyakan efisiensi operasi di sini, misalnya pembagian 4 dengan 2 membutuhkan hingga 90 langkah. Meskipun sangat tidak efisien tapi mampu menjelaskan operasi matematika secara logis.

Kita ambil contoh operasi penjumlahan, 2 + 1, yang hasilnya = 3. Secara input program adalah “+011010”.

Q 0  0  Q 1  0  R  011010000000
Q 1  1  Q 1  1  R  011010000000
Q 1  1  Q 1  1  R  011010000000
Q 1  0  Q 2  0  R  011010000000
Q 2  1  Q 3  0  L  011000000000
Q 3  0  Q 1  1  R  011100000000
Q 1  0  Q 2  0  R  011100000000
Q 2  0  Q99  0  N  011100000000

Operasi lain adalah pembagian, 4 : 2, yang hasilnya = 2. Secara input program adalah “:011110110”.

Q 0  0  Q 1  0  R  0111101100000000
Q 1  1  Q 2  1  R  0111101100000000
Q 2  1  Q 2  1  R  0111101100000000


Q17  0  Q18  0  R  0000000001110000
Q18  0  Q18  0  R  0000000001110000
Q18  1  Q99  0  N  0000000000110000

Berikut program dan aturan operasi matematis sesuai cara kerja mesin turing. Program dibuat menggunakan Borland Pascal 7.0. Penjelasan tentang program dapat dibaca langsung, meskipun agak susah dibaca. Maklum, dulu gemar membuat program yang sulit dibaca. Meskipun ketika dicoba saat ini tetap berjalan dengan baik.


{$S-,R-,G+,I+,X+,Q-,A+,B-}
{$M 7505,0,0}
{// Simulator Mesin Turing v1.03.001
 // Kompiler: Borland Pascal 7.0
 // Tanggal:  4 Agustus 1997
 // Nama:     MAYKADA HARJONO KURNIAWAN
 // NIM:      9311500174
 // Kelompok: P
}
program Simulator_Mesin_Turing;
type
  R_Aturan = record
    Q: Byte;       {Status}
    I: Char;       {Isian}
    G: ShortInt;   {Gerak}
  end;
  R_Atur = array[0..0,'0'..'1'] of R_Aturan;
  R_Khoirul = record
    Sdx: Byte;
    Qas: string[2];
    _t1: Char;
    Inp: Char;
    _t2: Char;
    Qhs: string[2];
    _t3: Char;
    Oup: Char;
    _t4: Char;
    Ges: Char;
  end;
  R_OpsAtur = record
    Ops: Char;
    Lok: ^R_Atur;
  end;
  R_Rul = ^R_Khoirul;
const
  Gerak: array[-1..1] of Char =
    ('L','N','R');
  SS_Ops: string[2] = 'x|';
var
  {-- maks 120 aturan --}
  Buf_Rul: array[1..120] of R_Atur;
  {-- maks 10 operasi --}
  Ops_Rul: array[1..10] of R_OpsAtur;
  {-- maks 60 Char --}
  Buf_S: string[60];
  IRul,Orul: Integer;
  Ops: Char;
  S_Ops: string[20];

procedure Parser_Fi_Dat;
var
  F1: Text;
  S: string[15];
  I,Idx,Qs,Kode: Word;
  Rul: ^R_Atur;
begin
  Assign(F1,'RUL.DAT');
  Reset(F1);
  I := 0;
  IRul := 1;
  Orul := 1;
  Rul := @Buf_Rul;
  S_Ops := '';
  FillChar(Buf_Rul,SizeOf(Buf_Rul),$FF);
  while not EoF(f1) do begin
    ReadLn(F1,S);
    case S[1] of
      '[':
      begin
        Rul := @Buf_Rul[IRul];
        with Ops_Rul[Orul] do begin
          Ops := S[2];
          Lok := @Rul^;
        end;
        SS_Ops[1] := S[2];
        S_Ops := S_Ops+SS_Ops;
        Inc(Orul);
      end;
      'q':
      begin
        with R_Rul(@S)^ do begin
          Qas[0] := #2;
          Qhs[0] := #2;
          Val(Qas,Idx,Kode);
          Val(Qhs,Qs,Kode);
          with Rul^[Idx,Inp] do begin
            Q := Qs;
            I := Oup;
            case Ges of
              'R': G := +1;
              'L': G := -1;
              'N': G := 00;
            end;
          end;
        end;
        Inc(IRul);
      end;
    end;
  end;
  Dec(S_Ops[0]);
  Close(F1);
end;

procedure Mesin(Op:Char);
var
  Ia,Id,Qs,Bar: Integer;
  Rul: ^R_Atur;
begin
  Ia := 1;
  while (Ops_Rul[Ia].Ops <> Op) and (Ia < Orul) do
    Inc(Ia);
  if (Ia=Orul) then Exit;
  Rul := @Ops_Rul[Ia].Lok^;
  Id := 1;
  Qs := 0;
  Bar := 1;
  repeat
    Ia := Id;
    Write('Q',Qs:2,'  ',Buf_S[Id]);
    with Rul^[Qs,Buf_S[Id]] do begin
      Qs := Q;
      Buf_S[Id] := I;
      Inc(Id,G);
    end;
    WriteLn('  Q',Qs:2,'  ',Buf_S[Ia],Gerak[Id-Ia]:3,'  ',Buf_S);
    Inc(Bar);
    if (Bar > 24) then begin
      Write('  Tekan Enter...');
      ReadLn;
      Bar := 1;
    end;
  until (Qs>98) or (Id>length(Buf_S));
end;

begin
  WriteLn('Simulator Mesin Turing  v1.03.001');
  Parser_Fi_Dat;
  repeat
    Write(#10#13'Sintak: [',S_Ops,']0x0x0, Misal: +0110110'#10#13,':) ');
    FillChar(Buf_S,SizeOf(Buf_S),'0');
    ReadLn(Buf_S);
    if (Buf_S='') then Exit;
    Ops := Buf_S[1];
    Delete(Buf_S,1,1);
    Buf_S[0] := Chr(SizeOf(Buf_S)-1);
    Mesin(Ops);
  until false;
end.

File RUL.DAT berisi aturan operasi.

//---- Format Input Kolom 1 -----------
// [ = Mulai Aturan Baru (Kol.2)
// q = Definisi Aturan (Bentuk Terpola)
// Lainnya = Tidak Diproses
// NB: Hasil q99  = Sukses dan Diterima
//     Hasil q255 = Gagal
// Org.(c).07.1997.mhk
//-------------------------------------
[+]
q00-0-q01-0-R
q01-0-q02-0-R
q02-0-q99-0-N
q01-1-q01-1-R
q02-1-q03-0-L
q03-0-q01-1-R
[-]
q00-0-q01-0-R
q01-0-q02-0-R
q02-0-q99-0-N
q02-1-q02-0-R
q01-1-q03-1-R
q03-1-q03-1-R
q03-0-q04-0-R
q04-0-q05-0-L
q05-0-q99-0-N
q04-1-q04-1-R
q05-1-q06-0-L
q06-1-q06-1-L
q06-0-q07-0-L
q07-1-q07-1-L
q07-0-q08-0-R
q08-1-q00-0-N
[*]
q00-0-q01-0-R
q01-1-q02-0-R
q01-0-q07-0-R
q07-1-q07-0-R
q07-0-q99-0-N
q02-0-q99-0-L
q02-1-q03-1-R
q03-1-q03-1-R
q03-0-q04-0-R
q04-0-q05-0-L
q04-1-q08-1-R
q05-0-q06-0-L
q06-1-q06-0-L
q06-0-q99-0-N
q08-1-q08-1-R
q08-0-q09-0-R
q09-1-q08-1-N
q09-0-q10-0-N
q10-0-q11-1-L
q11-0-q12-0-L
q11-1-q11-1-L
q12-1-q13-0-L
q12-0-q12-0-L
q13-0-q16-0-R
q13-1-q14-1-R
q14-0-q14-0-R
q14-1-q15-1-R
q15-1-q15-1-R
q15-0-q10-0-N
q16-0-q16-1-R
q16-1-q17-1-L
q17-1-q18-0-N
q18-1-q18-1-L
q18-0-q19-0-L
q19-1-q18-1-N
q19-0-q20-0-R
q20-0-q21-0-R
q21-1-q22-0-R
q22-0-q23-0-N
q22-1-q08-1-R
q23-0-q24-0-R
q24-1-q24-1-R
q24-0-q25-0-R
q25-0-q99-0-N
q25-1-q26-1-L
q26-0-q27-1-L
q27-1-q27-1-L
q27-0-q28-0-R
q28-1-q23-0-N
[:]
q00-0-q01-0-R
q01-1-q02-1-R
q01-0-q19-0-R
q02-1-q02-1-R
q02-0-q03-0-R
q03-0-q20-0-L
q03-1-q04-1-R
q04-1-q04-1-R
q04-0-q13-0-R
q13-0-q14-1-L
q13-1-q13-1-R
q14-0-q05-0-L
q14-1-q14-1-L
q05-1-q06-0-L
q06-1-q06-1-L
q06-0-q07-0-L
q07-1-q07-1-L
q07-0-q08-0-R
q08-1-q09-0-R
q08-0-q17-0-R
q09-1-q09-1-R
q09-0-q10-0-R
q10-0-q15-1-R
q10-1-q11-1-R
q11-1-q11-1-R
q11-0-q12-0-L
q12-1-q05-1-N
q15-0-q15-1-R
q15-1-q16-1-L
q16-1-q04-0-N
q17-1-q17-0-R
q17-0-q18-0-R
q18-0-q18-0-R
q18-1-q99-0-N
q19-1-q19-0-R
q19-0-q99-0-N
q20-0-q21-0-L
q21-1-q21-0-L
q21-0-q99-0-N

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s