Przykładowe programy


Inne rozdziały:

Poniżej przedstawiamy wraz z opisem kilka prostych programów dla maszyny Turinga. Możesz je skopiować do schowka i uruchomić wklejając do edytora naszego symulatora umieszczonego w następnym rozdziale tego opracowania. Zachęcamy gorąco do eksperymentów. A może samodzielnie ułożysz jakiś ciekawy program, którym chciałbyś się pochwalić na łamach naszego Serwisu Edukacyjnego? Zapraszamy.

 

Przesuwanie bitów o 1 w lewo

Zadaniem programu będzie przesunięcie bitów liczby binarnej o 1 w lewo, czyli np. z liczby 1101(2) powinniśmy otrzymać liczbę 11010(2). Operacja taka jest równoważna pomnożeniu wartości liczby przez 2. Cyfry liczby zostaną umieszczone w kolejnych komórkach taśmy. Przed wykonaniem programu głowica ustawi się na ostatniej cyfrze. Na znak pusty wybieramy pytajnik.

Maszyna może znajdować się w jednym z trzech stanów:

  1. q0 - wypisuje w bieżącej komórce taśmy symbol 0
  2. q1 - wypisuje w bieżącej komórce taśmy symbol 1
  3. q2 - stan końcowy.
Program
** Przesuwanie bitów liczby binarnej o 1 w lewo
** (C)2004 mgr Jerzy Wałaszek
** I LO w Tarnowie
************************************************
0,q0,0,q0,L stan początkowy, zapamiętujemy 0
1,q0,0,q1,L stan początkowy, zapamiętujemy 1
0,q1,1,q0,L zapisujemy zapamiętane 1,zapamiętujemy 0
1,q1,1,q1,L zapisujemy zapamiętane 1,zapamiętujemy 1
?,q0,0,q2,L koniec, zapisujemy zapamiętane 0
?,q1,1,q2,L koniec, zapisujemy zapamiętane 1


Jak to działa? To proste. Maszyna umieszcza w bieżącej komórce taśmy zapamiętane z poprzedniej pozycji cyfry binarne. Cyfry zapamiętywane są w stanie maszyny. Jeśli odczytanym symbolem jest 0, maszyna przechodzi w stan q0 i w następnym ruchu wypisze w sąsiedniej komórce 0. Jeśli odczytany symbol to 1, maszyna przechodzi w stan q1 i w następnym ruchu wypisze 1. W bieżącej komórce zapisuje 0 lub 1 w zależności od swojego bieżącego stanu, przy którym rozpoczęto wykonywanie instrukcji. Jeśli skończą się cyfry, to maszyna zapisuje to, co zapamiętała z poprzedniej komórki i przechodzi w stan końcowy.

Sprawdźmy działanie programu dla danych wejściowych 110101:


Taśma z głowicą Odczytany
znak
Stan
bieżący
Wykonywana operacja Zapisywany
znak
Nowy
stan
 ? ? 1 1 0 1 0 1 ? 
1 q0 1,q0,0,q1,L 0 q1
? 1 1 0 1 0 0 ? 
0 q1 0,q1,1,q0,L 1 q0
 ? ? 1 1 0 1 1 0 ? 
1 q0 1,q0,0,q1,L 0 q1
 ? ? 1 1 0 0 1 0 ? 
0 q1 0,q1,1,q0,L 1 q0
 ? ? 11 0 1 0 ? 
1 q0 1,q0,0,q1,L 0 q1
 ? ? 1 0 1 0 1 0 ? 
1 q1 1,q1,1,q1,L 1 q1
 ? ? 1 0 1 0 1 0 ? 
? q1 ?,q1,1,q2,L 1 q2
1 1 0 1 0 1 0 ? 
? q2 brak instrukcji, koniec    

 


Z ciągu wejściowego 110101 otrzymaliśmy ciąg wyjściowy 1101010, zatem cyfry binarne zostały przesunięte o 1 pozycję w lewo. Program spełnił swoje zadanie.

 

Zwiększanie liczby binarnej o 1

Liczba binarna będzie zapisywana na taśmie w postaci ciągu symboli 0 i 1. Znakiem pustym jest znak pytajnika. Przed wykonaniem programu głowica musi być ustawiona na pierwszej cyfrze liczby od prawej strony. Zanim ułożymy program, przyjrzyjmy się zasadom zwiększania o 1 liczby binarnej. Zwiększanie rozpoczynamy zawsze od ostatniej cyfry.


L.p. Przykład Opis
Reguła 1
  110010
+      1
  110011 
Jeśli ostatnią cyfrą jest 0, to zamieniamy je na 1 i kończymy. Reszta bitów pozostaje bez zmian.
Reguła 2
  110001
+      1
  110010 
Jeśli ostatnią cyfrą jest 1, to zamieniamy je na 0.  Do następnej pozycji należy dodać 1. Taką sytuację nazywamy stanem przeniesienia. W tym przypadku działanie przenosimy do kolejnej pozycji w lewą stronę.
Reguła 3
  110001
+      1
  110010 
Jeśli kolejną cyfrą jest 0 i występuje stan przeniesienia, zamieniamy ją na 1 i kończymy. Reszta bitów pozostaje bez zmian.
Reguła 4
  110011
+      1
  110100 
Jeśli kolejną cyfrą jest 1 i występuje stan przeniesienia, to zamieniamy ją na 0, utrzymujemy stan przeniesienia i przesuwamy się na kolejną pozycję po lewej stronie. Dla nowej pozycji znów będą obowiązywały reguły 3 i 4.
Reguła 5
      11
+      1
     100 
Jeśli skończyły się cyfry (natrafiliśmy na znak pusty) i występuje stan przeniesienia, to znak pusty zamieniamy na cyfrę 1 i kończymy.


Mając taką analizę każdą regułę kodujemy odpowiednią instrukcją dla maszyny Turinga.


L.p. instrukcja Opis
Reguła 1
0,g0,1,q2,L
W stanie początkowym q0 symbol 0 przechodzi w 1. Stan q0 zmienia się na stan q2. Zwróć uwagę, iż żadna instrukcja nie wykorzystuje tego stanu. Zatem dla dowolnego symbolu wejściowego maszyna Turinga zatrzyma wykonywanie programu.
Reguła 2
1,q0,0,q1,L
Jeśli w stanie początkowym odczytanym symbolem będzie 1, to zmieni się ona na 0, a maszyna przejdzie w stan q1, czyli w stan przeniesienia. Program nie zatrzyma się. Głowica zostanie przesunięta w lewo do sąsiedniej komórki, czyli do następnej cyfry w zapisie liczby.
Reguła 3
0,q1,1,q2,L
Jeśli w stanie przeniesienia q1 odczytany zostanie symbol 0, to maszyna zmieni go na 1 i przejdzie w stan końcowy, który spowoduje w następnym kroku zatrzymanie programu.
Reguła 4
1,q1,0,q1,L
Jeśli w stanie przeniesienia q1 odczytany zostanie symbol 1, to maszyna zamieni go na symbol 0, utrzyma stan przeniesienia q1 i przejdzie do następnej pozycji w zapisie liczby.
Reguła 5
?,q1,1,q2,L
Jeśli w stanie przeniesienia q1 natrafimy na koniec zapisu liczby (czyli znak pusty), to maszyna zapisze w bieżącej komórce taśmy symbol 1 i przejdzie w stan końcowy. Program zakończy się w następnym kroku


Zatem kompletny program wygląda następująco:


Program
** Zwiększanie liczby binarnej o 1
** (C)2004 mgr Jerzy Wałaszek
** I LO w Tarnowie
************************************************
0,q0,1,q2,L do 0 dodajemy 1 i kończymy
1,q0,0,q1,L do 1 dodajemy 1 i przeniesienie
0,q1,1,q2,L do 0 dodajemy przeniesienie i koniec
1,q1,0,q1,L do 1 dodajemy przeniesienie i dalej
?,q1,1,q2,L zapisujemy przeniesienie i koniec


Prześledźmy jego działanie dla liczby binarnej  1011(2) = 11(10). Głowicę ustawiamy na ostatniej cyfrze zapisu liczby. Maszyna startuje w stanie q0.


Taśma z głowicą Odczytany
znak
Stan
bieżący
Wykonywana operacja Zapisywany
znak
Nowy
stan
 ? 1 0 1 1 ? 
1 q0 1,q0,0,q1,L 0 q1
 ? 1 0 1 0 ? 
1 q1 1,q1,0,q1,L 0 q1
 ? 1 0 0 0 ? 
0 q1 0,q1,1,q2,L 1 q2
 ? 1 1 0 0 ? 
1 q2 brak instrukcji - koniec    


Otrzymaliśmy liczbę binarną 1100(2) = 12(10). Program spełnił swoje zadanie.

 

Zamiana liczby U2 na przeciwną

Kod U2 umożliwia zapis liczb ze znakiem. Dokładne omówienie zasad tworzenia tego kodu znajdziecie w naszym artykule o systemach liczbowych. Definicja liczby przeciwnej jest następująca:

 

Liczba b jest liczbą przeciwną do liczby a, jeśli a + b = 0

 

Istnieje kilka metod znajdowania liczby przeciwnej w kodzie U2. Na nasz użytek wybierzemy metodę następującą:


Algorytm wyznaczania liczby przeciwnej w kodzie U2
  1. Rozpoczynamy od ostatniej cyfry zapisu liczby.
  2. Jeśli bieżąco przetwarzana cyfra jest cyfrą 0, pozostawiamy ją bez zmian, przemieszczamy się o 1 pozycję w lewo i wracamy do punktu 2.
  3. Jeśli cyfry się skończyły (natrafiliśmy na znak pusty), kończymy
  4. Napotkaną cyfrę 1 zostawiamy bez zmian i przenosimy się o 1 pozycję w lewo.
  5. Jeśli cyfry się skończyły, kończymy.
  6. Bieżącą cyfrę zmieniamy na przeciwną, przenosimy się o 1 pozycję w lewo i wracamy do punktu 5.


Chociaż algorytm wydaje się na pierwszy rzut oka nieco zawiły, to jednak jest bardzo prosty. Oto przykład:

Znajdziemy liczbę przeciwną do  00101000(U2) = 40(10).


00101000
Rozpoczynamy od ostatniej cyfry. Pomijamy wszystkie cyfry 0.
00101000
Pierwszą napotkaną cyfrę 1 pozostawiamy bez zmian.
11011000
Od tego momentu wszystkie pozostałe cyfry zmieniamy na przeciwne.
11011000
Otrzymana liczba ma wartość przeciwną w kodzie U2. Sprawdzamy:
1x(-27) + 1x26 + 0x25 + 1x24 + 1x23 + 0x22 + 0x21 + 0x20 =
1x(-128) + 1x64 + 1x16 + 1x8 =
-128 + 64 + 16 + 8 = - 40, zgadza się.


Wynika z tego, iż maszyna Turinga odczytując cyfry 0 nie powinna zmieniać swojego stanu. Po napotkaniu pierwszej cyfry 1 stan maszyny powinien się zmienić. Teraz w tym nowym stanie wszystkie cyfry powinny być zmieniane na przeciwne. Oto odpowiedni program:


Program
** Zamiana liczby U2 na przeciwną
** (C)2004 mgr Jerzy Wałaszek
** I LO w Tarnowie
************************************************
0,q0,0,q0,L pomijamy początkowe 0
1,q0,1,q1,L pierwsze 1 pozostawiamy bez zmian
0,q1,1,q1,L pozostałe bity zmieniamy
1,q1,0,q1,L na przeciwne


Dla przykładu prześledźmy działanie tego programu dla liczby 1110(U2) = -2. Głowicę ustawiamy na ostatniej cyfrze zapisu liczby. Maszyna rozpoczyna wykonywanie programu od stanu q0.


Taśma z głowicą Odczytany
znak
Stan
bieżący
Wykonywana operacja Zapisywany
znak
Nowy
stan
 ? 1 1 1 0 
0 q0 0,q0,0,q0,L 0 q0
 ? 1 1 1 0 ? 
1 q0 1,q0,1,q1,L 1 q1
 ? 1 1 1 0 ? 
1 q1 1,q1,0,q1,L 0 q1
 ? 1 0 1 0 ? 
1 q1 1,q1,0,q1,L 0 q1
 ? 0 0 1 0 ? 
? q1 brak instrukcji - koniec    


Otrzymaliśmy liczbę 0010(U2) = 2, a więc przeciwną do 1110(U2) = -2. Program spełnił swoje zadanie.

 

Dodawanie bitu parzystości

W transmisjach cyfrowych pojawiają się błędy polegające na tym, iż odbiornik odczytuje zakłócone bity ze stanem przeciwnym, tzn. jeśli nadano bit o wartości 1, odczytane zostaje 0 i na odwrót. Na występowanie zakłóceń zwykle nie mamy wpływu - mogą to być np. wyładowania elektryczne w trakcie burzy, iskrzenie w układach elektrycznych maszyny pracującej w pobliżu toru transmisyjnego, różne zakłócenia losowe. Dlatego transmisję zabezpiecza się przy pomocy różnych kodów, które umożliwiają odbiornikowi wykrycie błędu w odebranych danych (kody detekcyjne) lub poprawienie błędu (kody korekcyjne).

Najprostszym rodzajem kodu detekcyjnego jest bit parzystości. Do przesyłanych danych dodajemy dodatkowy bit o takiej wartości 0 lub 1, aby liczba bitów 1 w przesyłanym słowie była parzysta. Jeśli teraz wystąpi przekłamanie w odbiorze, to odbiornik zliczając otrzymane bity o wartości 1 otrzyma liczbę nieparzystą, ponieważ jeden z bitów zmienił się na przeciwny Stąd będzie wiadome, iż odebrana informacja jest błędna - odbiornik w takim przypadku może połączyć się kanałem zwrotnym z nadajnikiem i zażądać ponowienia transmisji danych.

Zasada wyznaczania bitu parzystości jest bardzo prosta:


Algorytm wyznaczania bitu parzystości
  1. Rozpoczynamy od ostatniego bitu. Bit parzystości wstępnie ustawiamy na 0.
  2. Jeśli bieżącą cyfrą jest 0, przesuwamy się do kolejnej pozycji w lewo i wracamy do punktu 2.
  3. Jeśli bieżącą cyfrą jest 1, zmieniamy stan bitu parzystości na przeciwny, przesuwamy się w lewo i wracamy do punktu 2.
  4. Jeśli cyfry się skończyły, dopisujemy bit parzystości i kończymy.

 

W programie dla maszyny Turinga stan bitu parzystości będziemy kodowali stanami: q0 - stan 0 i q1 - stan 1.

 

Program
** Bit parzystości
** (C)2004 mgr Jerzy Wałaszek
** I LO w Tarnowie
************************************************
0,q0,0,q0,L bity 0 ignorujemy
1,q0,1,q1,L bity 1 uzupełniamy do parzystych
0,q1,0,q1,L bity 0 ignorujemy
1,q1,1,q0,L bity 1 uzupełniamy do parzystych
?,q0,0,q2,L zapisujemy wynikowy bit
?,q1,1,q2,L parzystości

 

Dla przykładu prześledźmy działanie tego programu dla danych binarnych 110100. Głowicę ustawiamy na ostatniej cyfrze zapisu liczby. Maszyna rozpoczyna wykonywanie programu od stanu q0.

 

Taśma z głowicą Odczytany
znak
Stan
bieżący
Wykonywana operacja Zapisywany
znak
Nowy
stan
 ? ? 1 1 0 1 0 0 
0 q0 0,q0,0,q0,L 0 q0
 ? ? 1 1 0 1 0 0 ? 
0 q0 0,q0,0,q0,L 0 q0
 ? ? 1 1 0 1 0 0 ? 
1 q0 1,q0,1,q1,L 1 q1
 ? ? 1 1 0 1 0 0 ? 
0 q1 0,q1,0,q1,L 0 q1
 ? ? 1 1 0 1 0 0 ? 
1 q1 1,q1,1,q0,L 1 q0
 ? ? 1 1 0 1 0 0 ? 
1 q0 1,q0,1,q1,L 1 q1
 ? ? 1 1 0 1 0 0 ? 
? q1 ?,q1,1,q2,L 1 q2
 ? 1 1 1 0 1 0 0 ? 
? q2 brak instrukcji, koniec    

 

Otrzymaliśmy wynik 1110100 - liczba jedynek wynosi 4, czyli jest parzysta.

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.