Лабороторна робота №2

Завдання: Програмно реалізувати основні інструкції з набору елементарних операцій для машини Тьюрінга.



A

B

C

D

E

F

G

H

I



1.Реалізувати графічно задану конфігурацію машини Тьюрінга. (Мова програмування довільна)

2. Програмно реалізувати функцію переходів. Новий стан, новий символ, напрям руху задає користувач.

3. Зупинка машини відбувається в тому випадку, якщо для пари (стан, символ) функція переходу не визначена.

Теоретичні відомості

Машина Тьюринга (МТ) - абстрактний виконавець (абстрактна обчислювальна машина). Була запропонована Аланом Тьюрингом в 1936 для формалізації поняття алгоритму.

Машина Тьюринга є розширенням кінцевого автомата і, згідно тези Черча - Тьюринга, здатна імітувати всі інші виконавці (за допомогою завдання правил переходу), яким-небудь чином реалізують процес покрокового обчислення, в якому кожен крок обчислення досить елементарний

До складу машини Тьюрінга входить нескінченна в обидві сторони стрічка (можливі машини Тьюринга, які мають кілька нескінченних стрічок), розділена на осередки, і керуючий пристрій, здатне знаходитися в одному з безлічі станів. Число можливих станів керуючого пристрою звичайно і точно задано.

Керуючий пристрій може переміщатися вліво і вправо по стрічці, читати і записувати в осередки стрічки символи деякого кінцевого алфавіту. Виділяється особливий порожній символ, що заповнює всі клітини стрічки, окрім тих з них (кінцевого числа), на яких записані вхідні дані.

Керуючий пристрій працює згідно з правилами переходу, які представляють алгоритм, реалізований даною машиною Тьюринга. Кожне правило переходу наказує машині, в залежності від поточного стану і спостережуваного в поточній клітині символу, записати в цю клітку новий символ, перейти в новий стан і переміститися на одну клітку вліво або вправо. Деякі стану машини Тьюринга можуть бути помічені як термінальні, і перехід в будь-яке з них означає кінець роботи, зупинку алгоритму.

Машина Тьюринга називається детермінованою, якщо кожній комбінації стану і стрічкового символу в таблиці відповідає не більше одного правила. Якщо існує пара "стрічковий символ - стан", для якої існує 2 і більше команд, така машина Тьюринга називається недетермінованої.

Конкретна машина Тьюринга задається перерахуванням елементів множини букв алфавіту A, безлічі станів Q і набором правил, за якими працює машина. Вони мають вигляд: q _i a _j → q _i1 a _j1 d _k (якщо головка знаходиться в стані q _i, а в оглядається комірці записана буква a _j, то головка переходить в стан q _i1, в клітинку замість a _j записується a _j1, головка робить рух d _k, яке має три варіанти: на клітинку вліво (L), на клітинку вправо (R), залишитися на місці (N)). Для кожної можливої конфігурації i, a _j> є рівно одне правило. Правил немає тільки для заключного стану, потрапивши в яку машина зупиняється. Крім того, необхідно вказати кінцеве і початкове стану, початкову конфігурацію на стрічці і розташування голівки машини.

Пояснення до завдання:

Програма повинна мати графічне представлення машини Тьюринга, яке включає в себе стрічку, каретку, поля для введення символів та номерів комірок та керуючі кнопки. Програма повинна замінювати символ в заданій комірці на вказаний вами символ. Відшукувати вказані вами сиволи та замінювати їх на задані.

Код програми:

unit Unit3;

interface

uses

Winapi.Windows, Winapi.Messages, System.SysUtils, System.Variants, System.Classes, Vcl.Graphics,

Vcl.Controls, Vcl.Forms, Vcl.Dialogs, Vcl.StdCtrls, Vcl.ExtCtrls,

Vcl.Imaging.jpeg, Vcl.Buttons, Vcl.Mask, Vcl.Grids, Vcl.ValEdit, Vcl.Menus,

Vcl.Imaging.pngimage;

type

TForm3 = class(TForm)

Edit1: TEdit;

Edit2: TEdit;

Edit3: TEdit;

Edit4: TEdit;

Edit5: TEdit;

Edit6: TEdit;

Edit7: TEdit;

Edit8: TEdit;

Edit9: TEdit;

Edit10: TEdit;

Edit17: TEdit;

Image1: TImage;

Edit18: TEdit;

Edit19: TEdit;

Edit20: TEdit;

Button1: TButton;

Button2: TButton;

Edit12: TEdit;

Label1: TLabel;

Label2: TLabel;

Label3: TLabel;

MainMenu1: TMainMenu;

N1: TMenuItem;

N2: TMenuItem;

Label4: TLabel;

Label5: TLabel;

procedure FormCreate(Sender: TObject);

procedure Button1Click(Sender: TObject);

procedure Button2Click(Sender: TObject);

procedure N1Click(Sender: TObject);

procedure N2Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form3: TForm3;

implementation

{$R *.dfm}

var n,i:integer; a:array[1..15] of TEdit;

procedure TForm3.Button1Click(Sender: TObject);

var n1,i:integer; s:char;

begin

n1:=strtoint(Edit18.Text);

if (n1>=1)and(n1<=9) then

begin

image1.Left:=39-31+(n1*31);

a[n1].Text:=Edit19.Text;

end

else showmessage('Error!!!');

end;

procedure TForm3.Button2Click(Sender: TObject);

var s:string;

begin

for i := 1 to 9 do begin

if a[i].Text=Edit20.text then a[i].Text:=Edit12.Text;

end;

end;

procedure TForm3.FormCreate(Sender: TObject);

begin

a[1]:=Edit2; a[2]:=Edit3; a[3]:=Edit4;

a[4]:=Edit5; a[5]:=Edit6; a[6]:=Edit7; a[7]:=Edit8; a[8]:=Edit9;

a[9]:=Edit10;

end;

procedure TForm3.N1Click(Sender: TObject);

begin

Button2.Visible:=False;

Edit20.Visible:=False;

Edit12.Visible:=False;

Button1.Visible:=True;

Edit18.Visible:=True;

Edit19.Visible:=true;

Label1.Visible:=True;

Label2.Visible:=True;

Label4.Visible:=False;

Label5.Visible:=False;

end;

procedure TForm3.N2Click(Sender: TObject);

begin

Button2.Visible:=True;

Edit20.Visible:=True;

Edit12.Visible:=True;

Button1.Visible:=False;

Edit18.Visible:=False;

Edit19.Visible:=False;

Label4.Visible:=True;

Label5.Visible:=True;

Label1.Visible:=False;

Label2.Visible:=False;

end;

begin

n:=1;

end.

Пояснення до виконаного завдання:

- в поле «Перемістити на» вводиться номер комірки в поле “замінити на” вводится символ який потрібно вставити в комірку з номером, який ви ввели “Перемістити на”.

П ри натискувані на кнопку “Перемістити”, каретка - переміщається на задану комірку і заміняє символ в комірці на задан.

- при натискуванні програма виглядає:

в поле «З» вводится символ який потрібно замінити , а в поле “На” вводится сивол на який потрібно замінити заданий сивол. При натискуванні на кнопку “Замінити” програма шукає символ вказаний у полі “З” та заміняє на сивол вказаний у полі “На”.

При натисуванні на пункт меню -програма повертається в початкову конфігурацію.