Maszyna Turinga
Alan Mathison Turing (ur. 23 czerwca 1912 w Londynie 
zm. 7 czerwca 1954 w Wilmslow) 
angielski matematyk, twórca maszyny Turinga
i jeden z twórców informatyki.
Budowa maszyny Turinga
Alan Turing pod koniec lat trzydziestych
ubiegłego wieku na potrzeby swoich badań
nad problemami obliczalności opracował
model maszyny, który mo\
na zrealizować
nawet na kartce papieru.
Był to automat abstrakcyjny, słu\
ący do
analizy algorytmów.
Maszyna Turinga zbudowana jest z trzech
głównych elementów:
1. Nieskończonej taśmy zawierającej komórki
z przetwarzanymi symbolami.
2. Ruchomej głowicy zapisująco-odczytującej.
3. Układu sterowania głowicą.
... A A C C D D 0 1 2 3 E F G Z ? ? ...
Nieskończona taśma jest odpowiednikiem
współczesnej pamięci komputera. Taśma dzieli
się na komórki, w których umieszczone zostały
symbole, czyli po prostu znaki przetwarzane
przez maszynę Turinga. Symbole te stanowią
odpowiednik danych wejściowych. Maszyna
Turinga odczytuje te dane z kolejnych komórek
i przetwarza na inne symbole, czyli dane
wyjściowe. Wyniki obliczeń równie\
są
zapisywane w komórkach taśmy.
Głowica zapisująco  odczytująca
Głowica ta odpowiada funkcjonalnie
urządzeniom wejścia/wyjścia współczesnych
komputerów lub układom odczytu i zapisu
pamięci.
Głowica zawsze znajduje się nad jedną
z komórek taśmy. Mo\
e ona odczytywać
zawartość tej komórki oraz zapisywać do niej
inny symbol - na tej zasadzie odbywa się
przetwarzanie danych - z jednych symboli
otrzymujemy inne. Oprócz odczytywania
i zapisywania symboli w komórkach głowica
wykonuje ruchy w prawo i w lewo do sąsiednich
komórek na taśmie. W ten sposób mo\
e się ona
przemieścić do dowolnie wybranej komórki
taśmy.
Układ sterowania
Układ sterowania głowicą zarządza
przetwarzaniem informacji. Jego współczesnym
odpowiednikiem jest procesor komputera. Układ
ten odczytuje za pomocą głowicy symbole
z komórek taśmy oraz przesyła do głowicy
symbole do zapisu w komórkach. Dodatkowo
nakazuje on głowicy przemieścić się do
sąsiedniej komórki w lewo lub w prawo.
Podstawą działania maszyny Turinga są stany
układu sterowania. Stan układu sterowania
określa jednoznacznie jaką operację wykona,
oraz jak zareaguje maszyna Turinga, gdy
odczyta z taśmy określony symbol.
Zatem operacje wykonywane przez układ
sterowania zale\
ą od dwóch czynników:
1. Symbolu odczytanego z komórki na taśmie.
2. Bie\
ącego stanu układu sterującego.
Stany zostały określone kolejnymi nazwami:
q0, q1, q2, ... ,qn, gdzie q0 jest stanem
początkowym, w którym znajduje się maszyna
Turinga przed rozpoczęciem przetwarzania
symboli na taśmie.
Przyjmijmy następującą składnię instrukcji
dla maszyny Turinga:
Instrukcja
maszyny Znaczenia symboli
Turinga
- symbol odczytany przez głowicę z
So
bie\
ącej komórki na taśmie
qi - bie\
ący stan układu sterowania
- symbol, jaki zostanie zapisany w
(So,qi,Sz,qj,L/R)
Sz
bie\
ącej komórce na taśmie
- nowy stan, w który przejdzie układ
qj
sterowania po wykonaniu tej operacji
- ruch głowicy o jedną komórkę w lewo
L/R
(L) lub w prawo (R)
S0 i qi są tzw. częścią identyfikacyjną
instrukcji. Maszyna Turinga wykonuje tyle
ró\
nych instrukcji, ile zdefiniujemy części
identyfikacyjnych - w programie nie mo\
e być
dwóch ró\
nych instrukcji o identycznej części
identyfikacyjnej.
Powód jest oczywisty - którą instrukcję
nale\
ałoby w takim wypadku wykonać?
Sz, qj i L/R są tzw. częścią operacyjną, która
określa jakie działanie podejmuje dana
instrukcja. Części operacyjne ró\
nych instrukcji
mogą być takie same - oznacza to jedynie, i\

instrukcje te wykonują dokładnie to samo
działanie.
Program dla maszyny Turinga
Aby lepiej zrozumieć działanie maszyny
Turinga, rozwa\
my następujący program
zło\
ony z dwóch instrukcji:
Program
0,q0,1,q0,L bit 0 zamień na 1
1,q0,0,q0,L bit 1 zamień na 0
Przyjmijmy równie\
, \
e fragment nieskończonej
taśmy zwiera następujący ciąg symboli:
... ? 1 0 1 1 0 ? ...
Symbolem pustym jest znak pytajnika. Dane do
przetworzenia przez program zawarte są w kolejnych
5 komórkach - 10110.
Załó\
my, i\
jest to jakaś wartość binarna.
Przed rozpoczęciem wykonywania programu
ustawiamy głowicę na określonej komórce taśmy.
W tym przypadku niech będzie to ostatni symbol
0:
... ? 1 0 1 1 0 ? ...
Po uruchomieniu maszyny Turinga obserwujemy
co się stanie:
Taśma z Odczytany Stan
Wykonywana operacja
głowicą znak bie\
ący
Kombinacja odczytanego znaku i stanu q0
wyznacza instrukcję 0,q0,1,q0,L. Zatem
znak w bie\
ącej komórce maszyna
0 q0
Turinga umieści symbol 1, stanu nie
? 1 0 1 1 0 ?
zmieni (wcią\
pozostanie w q0) i
przemieści głowicę do sąsiedniej komórki
po lewej stronie.
Teraz kombinacja odczytanego znaku i
stanu wewnętrznego wyznacza instrukcję
1,q0,0,q0,L. Znak w bie\
ącej komórce
1 q0
taśmy zostanie zastąpiony znakiem 0, stan
? 1 0 1 1 1 ?
wewnętrzny nie zmieni się i głowica
będzie przesunięta w lewo do następnej
komórki.
To samo, co powy\
ej, instrukcja
1 q0
? 1 0 1 0 1 ?
1,q0,0,q0,L.
0 q0 Instrukcja 0,q0,1,q0,L.
? 1 0 0 0 1 ?
1 q0 Instrukcja 1,q0,0,q0,L
? 1 1 0 0 1 ?
Ta instrukcja nie została zdefiniowana,
? q0
? 0 1 0 0 1 ?
zatem program zakończy swoją pracę
Maszyna Turinga,
a współczesny komputer
Odpowiednikiem procesora jest tu głowica,
pamięci - taśma, natomiast diagram przejść
między stanami odpowiada BIOS-owi,
Windowsowi lub innemu oprogramowaniu.
Przykład:
maszyna realizująca algorytm Euklidesa wyznaczania
NWD (Największy Wspólny Dzielnik) dwóch liczb:
function NWD (x0= 24, x1= 9: Word): Word;
repeat
x2:= x0 mod x1;
x0:= x1;
x1:= x2;
until (x2 = 0);
NWD:= x0
1. x2:= 6; x0:=9; x1:=6;
2. x2:= 3; x0:=6; x1:=3
3. x2:= 0; x0:=3; x1:=0;
4. NWD=3;
2-wymiarową Turing machine opracowano w latach
80-tych. Mrówka porusza się po siatce zawierającej
białe i czarne pola według następujących reguł:
1. Kiedy mrówka znajdzie się na polu czarnym obraca się
w prawo i przesuwa o jedno pole do przodu.
2. Kiedy mrówka jest na polu białym, obraca się w lewo
i przesuwa do przodu o jedno pole.
3. Kiedy mrówka opuszcza pole zmienia ono kolor.
Test Turinga
Test Turinga to sposób określania zdolności
maszyny do posługiwania się językiem
naturalnym i pośrednio mającym dowodzić
opanowania przez nią umiejętności myślenia
w sposób podobny do ludzkiego. Test ten został
zaproponowany w 1950 roku przez Alana
Turinga. Turing zaproponował ten test w celu
zamiany pełnego emocji i w jego pojęciu
bezsensownego pytania "Czy maszyny myślą?"
na pytanie lepiej zdefiniowane, w ramach badań
nad stworzeniem sztucznej inteligencji.
Test Turinga
Test wygląda następująco: sędzia - człowiek -
prowadzi rozmowę w języku naturalnym
z pozostałymi stronami. Jeśli sędzia nie jest
w stanie wiarygodnie określić, czy któraś ze
stron jest maszyną czy człowiekiem, wtedy mówi
się, \
e maszyna przeszła test. Zakłada się, \
e
zarówno człowiek jak i maszyna próbują przejść
test zachowując się w sposób mo\
liwie zbli\
ony
do ludzkiego.
SCHEMAT TESTU TURINGA
Test pochodzi od zabaw polegających na
zgadywaniu płci osoby znajdującej się
w innym pokoju przy pomocy serii pytań
i odpowiedzi pisanych na kartkach papieru.
W pierwotnym pomyśle Turinga człowiek musiał
udawać przeciwną płeć, a test był ograniczony
do pięciominutowej rozmowy. Dziś nie uwa\
a się
tych cech za podstawowe i zasadniczo nie
umieszcza w specyfikacji testu Turinga.
Turing oczekiwał, \
e maszyny w końcu będą
w stanie przejść ten test. Ocenił, \
e około roku
2000 maszyny z pamięcią o pojemności 109
bitów (około 119 MB) będą w stanie oszukać
30% sędziów w czasie pięciominutowego testu.
Przewidywał równie\
, \
e ludzie przestaną
uwa\
ać zdanie "myśląca maszyna" za
wewnętrznie sprzeczne. Oceniał, \
e uczenie
maszynowe nabierze du\
ego znaczenia
w budowaniu wydajnych maszyn. To twierdzenie
jest przez dzisiejszych badaczy sztucznej
inteligencji oceniane jako zasadne.
Spory o to, czy test Turinga we właściwy sposób
definiuje inteligencję maszynową (lub "myślenie
maszynowe") dotyczyły głównie trzech punktów:
1. Maszyna, która przejdzie test Turinga mo\
e być
w stanie symulować ludzkie zachowanie
konwersacyjne, lecz mo\
e to być znacznie mniej
ni\
prawdziwa inteligencja. Maszyna mo\
e
zwyczajnie u\
ywać sprytnie wymyślonych reguł.
Częstą ripostą w społeczności zajmującej się
badaniami nad sztuczną inteligencją jest
zadanie pytania "A skąd wiemy czy ludzie sami
po prostu nie posługują się jakimiś sprytnie
wymyślonymi regułami?".
2. Maszyna mo\
e być inteligentna nie posiadając
ludzkiej umiejętności prowadzenia rozmowy.
3. Wielu ludzi mogłoby nie być w stanie zaliczyć
takiego testu. Z drugiej strony, inteligencję
innych ludzi oceniamy zazwyczaj wyłącznie na
podstawie tego co i jak mówią.
Jak dotąd, \
aden komputer
nie zaliczył testu Turinga.
Co roku wyznaczana jest Nagroda Loebnera dla
najlepszych zawodników w teście Turinga.
Po raz pierwszy ograniczony test Turinga odbył
się w 1991 roku, w Bostońskim Muzeum
Komputerów. Sześć komputerów miało udawać
ludzi, a dwie osoby komputery. Wszystkie
terminale połączona ze sobą za pomocą
modemów i sieci telefonicznej. Dziesięciu
sędziów podchodziło kolejno do ka\
dego
terminala i brało udział w konwersacji
z niewiadomym partnerem. Wynik eksperymentu
był zaskoczeniem.
Zwycięzcą został program komputerowy
autorstwa Josepha Weintrauba, który jako temat
rozmów zadeklarował pogaduszki. A\
pięcioro
sędziów było przekonanych, \
e rozmawiało
z człowiekiem. Z kolei specjalista zajmujący się
twórczością Shakespeara został uznany przez
troje sędziów za program komputerowy, gdy\

zbyt szybko i dokładnie cytował jego dzieła
z pamięci. Zostało to odebrane jako odczyt
z pamięci masowej, w której zmagazynowane
zostały teksty utworów.
Maszyna
von Neumana
John von Neumann
W roku 1946 John von Neuman (1903-1957),
genialny amerykański uczony węgierskiego
pochodzenia (przede wszystkim matematyk, ale
tak\
e chemik, fizjolog, biolog, fizyk
i filozof) określił zasady, według których powinno
się konstruować komputery. Zasady te wytyczyły
nowy kierunek w historii komputerów i są
stosowane do dnia dzisiejszego.
Zasady von Neumana mo\
na zawrzeć w trzech
punktach:
1. instrukcje i dane mają być identycznie
reprezentowane w maszynie;
2. program i dane muszą mieścić się w tej samej
wewnętrznej pamięci (operacyjnej) komputera;
3. dzięki jednakowej reprezentacji danych i instrukcji
maszyna powinna móc wykonywać operacje na
instrukcjach i całym programie.
Taką architekturę komputera nazywano sterowaną
programem. Wobec tak sformułowanej definicji
komputera ENIAC wszystkie poprzedzające go
maszyny nie były komputerami.
Maszyna von Neumanna była komputerem w pełni
automatycznym, cyfrowym i uniwersalnym,
z wczytywanym programem. Jej wewnętrzna
architektura stała się wzorem dla komercyjnych maszyn
następnej generacji. Komputer posłu\
ył do wykonania
wielu obliczeń z dziedziny abstrakcyjnej matematyki,
fizyki i meteorologii. Pomógł zbadać wewnętrzną
strukturę gwiazd i stabilność orbit cząstek
w akceleratorach. Był naprawdę uniwersalny.
Schemat funkcjonalny komputera
von Neumanna
idea komputera sterowanego programem
Opis schematu maszyny
von Neumanna
" Procesor
" Pamięć
" Zegar
" Magistrale
" Wejście/Wyjście
Procesor (ang. processor) -
układ dokonujący operacji na danych
zgromadzonych w pamięci lub płynących z/do
urządzeń wejście/wyjście, sterowany
programem, którego kod znajduje się w pamięci.
Do przechowywania swojego wewnętrznego
stanu procesor wyposa\
ony jest w pewną ilość
rejestrów.
Do najwa\
niejszych rejestrów procesora nale\
ą:
" Wskaz
nik instrukcji (ang. instruction pointer) -
wskazuje komórkę pamięci, z której pobrany będzie
następna instrukcja do wykonania.
" Rejestr flag stanu (ang. flag register, flags) - składają
się na niego jednobitowe flagi przechowujące
informacje o stanie procesora (np. dopuszczalności
przerwań) lub rezultacie ostatnio wykonanej instrukcji.
" Wskaz
nik stosu (ang. stack pointer) - wskazuje
pierwszą wolną komórkę pamięci na stosie
procesora - strukturze danych typu FILO (ang.
first in last out - pierwszy przyszedł, ostatni
wyszedł) wykorzystywanej przy skokach do
podprogramów dla przechowywania adresu
powrotu i zmiennych lokalnych.
" Akumulator (ang. accumulator) - słu\
y jako
argument a zarazem miejsce umieszczania
rezultatów operacji arytmetycznych.
Pamięć (pamięć operacyjna,
ang. memory) -
przechowuje dane i kod prgramu. Je\
eli jej
konstrukcja umo\
liwia oprócz odczytu
dokonywanie w niej modyfikacji nazywamy ją
RAM (ang. random access memory), jeśli jej
konstrukcja pozwala jedynie na odczyt
nazywana jest ROM (ang. read only memory).
Pamięć dzieli się na komórki, z których
ka\
da jest w stanie przechować liczbę całkowitą
z ustalonego dla danej architektury zakresu.
Najczęściej jest to 0, 1,...,255. Do zakodowania
takich liczb potrzeba 8 bitów tj. 1 bajt. Ka\
da
komórka pamięci posiada unikalny numer zwany
adresem fizycznym, który słu\
y procesorowi do
odwoływania się do niej.
Zegar
odmierza cykle wykonywania instrukcji
programu.
Magistrale (ang. buses) -
słu\
ą do przesyłania danych i synchronizacji elementów
komputera:
1. Magistrala danych (ang. data bus) słu\
y do przesyłania
danych między pamięcią, układami we/wy,
a procesorem. Ilość u\
ytych tutaj linii (szerokość szyny)
jest równa długości słowa maszynowego i jest równa
rozmiarowi komórki pamięci, lub jest jego
wielokrotnością.
2. Magistrala adresów (ang. address bus) słu\
y
procesorowi do wysyłania numerów komórek pamięci
lub rejestrów we/wy na których będzie dokonane
następne przesłanie danych. Ilość u\
ytych tutaj linii
decyduje o ilości pamięci jaką mo\
na zaadresować.
3. Magistrala sterująca (ang. control bus) słu\
y do
wzajemnej synchronizacji oraz przekazywania
i potwierdzania przyjęcia/wykonania zleceń.
Wejście/Wyjście
Pozwala komputerowi kontaktować się
z zewnętrznym światem (klawiatura, monitor,
czytniki, adaptery sieciowe itp) lub
przechowywać dane poza pamięcią operacyjną
(dyski).
Na wejście/wyjście składają się następujące
układy i urządzenia:
1. Sprzętowe sterowniki wejścia - wyjścia.
Układy te potrafią się porozumiewać z
procesorem poprzez rejestry we/wy,
przerwania, kanały DMA i własną adresowalną
przez procesor pamięć układu. Wykonując
zlecenia procesora sterują urządzeniami
wejścia wyjścia. W technologii
mikrokomputerowej są montowane jako karty
rozszerzające wewnątrz obudowy komputera.
2. Urządzenia zewnętrzne - zapewniają kontakt
komputera ze światem. Mogą to być
klawiatury, monitory, dyski, drukarki, modemy
ale tak\
e czujniki i ramiona robotów w procesie
produkcyjnym.
3. Interfejsy. Interfejs jest to specyfikacja sposobu
przesyłania danych między dwoma
urządzeniami. Pojęcie to bywa często
przenoszone na realizację sprzętową interfejsu
w postaci gniazd, wtyków i kabli. Bywa te\

rozszerzane na komunikację człowiek-
maszyna, mówimy wtedy o interfejsie
u\
ytkownika.
Pierwsze pokolenie komputerów
" przeznaczone do rozwiązywania jednego zadania w trybie
pasywnym
" algorytm posiada stałą strukturę i jest wykonywany
sekwencyjnie
" funkcjonowanie określone zostaje na etapie projektowania
" brak systemu operacyjnego
" budowane w oparciu o lampy elektronowe
" funkcjonowały w latach 1945-1954
jednostka arytmetyczno-logiczna
ALU
Urządzenia
Pamięć
wejścia-wyjścia
główna
Jednostka sterująca
Struktura komputerów pierwszego pokolenia
Drugie pokolenie komputerów
" przeznaczone do rozwiązywania wielu zadań w trybie pasywnym
" zastosowano algorytm szeregowo-równoległy (elementy
współbie\
ności)
" zastosowano prosty system operacyjny (tzw. monitor)
" wykorzystanie pierwszych języków programowania
" po raz pierwszy zastosowano pamięć wirtualną
" budowane w oparciu o tranzystory
" funkcjonowały w latach 1955-1964
Procesor
centralny
Urządzenia
Multi- Kanały
peryferyjne
plekser danych
Pamięć
Struktura komputerów drugiego pokolenia
Trzecie pokolenie komputerów
" wykorzystywały algorytm sterowania, pozwalający ręcznie
zmieniać strukturę maszyny
" rozwinięto wieloprogramowalność i zastosowano podział czasu
" zastosowano tryb interakcyjny
" wykorzystanie języków wysokiego poziomu
" do budowy wykorzystywano układy scalone małego i średniego
stopnia scalania
" funkcjonowały w latach 1955-1964
Procesor
Interfejs pamięci
centralny
Pamięć
Interfejs procesora
operacyjna
Kanały
danych
Struktura komputerów trzeciego pokolenia
Czwarte pokolenie komputerów
" Algorytm sterowania procesem obliczeniowym pozwala na równoległe
rozwiązywanie szeregu problemów
" Struktura systemu automatycznie dostosowuje się do struktury
rozwiązywanego zadania
" W celu zwiększenia szybkości szerzej zastosowano sprzętowe metody
rozwiązywania niektórych problemów
" Budowane w oparciu o układy scalone o du\
ym stopniu integracji
" U\
ywane w latach 1970-1990
Pamięć operacyjna
Sieć połączeń
.......
Procesor 1 Procesor 2 Procesor n
Piąte pokolenie komputerów
" Pozwala rozwiązywać bardzo skomplikowane zadania
" Algorytm sterowania dopuszcza zmianę struktury systemu
obliczeniowego w trakcie rozwiązywania zadania
" U\
ywane języki programowania coraz bardziej zbli\
ają się do
języka naturalnego
" Wybrane funkcje realizuje się sprzętowo
Sieć połączeń
Procesor Procesor
skalarny wektorowy
Pamięć Pamięć
..........
operacyjna operacyjna
Układy wejścia wyjścia
Architektura komputera piątego pokolenia
Pięć pokoleń komputerów - zestawienie
Pokolenie Technologia Oprogramowanie Przykłady
i architektura I aplikacje
Pierwsze Lampy elektronowe, Tryb jednou\
ytkownikowy wsadowy ENIAC
1945-1954 Pamięć na liniach opóz
niających, Języki maszynowe Pronceton IAS
Procesor centralny sterowany przez Brak podprogramów IBM 701
licznik rozkazów i akumulator
We/wy obsługiwane przez procesor
Arytmetyka stałopozycyjna centralny
Drugie Tranzystory Elementy wieloprogramowości IBM 7090
1955-1964 Dyskretne pamięci rdzeniowe Języki Algol, Fortran  kompilatory CDC 1604
Arytmetyka zmiennopozycyjna Monitory (protoplasta SO) Univac LARC
Procesory we/wyj
Dzielony dostęp do pamięci
Trzecie Układy scalone (SSI oraz MSI) Wieloprogramowość i podział czasu IBM 360/370
1965-1974 Pamięć cache Języki PL/I, C, Cobol CDC 6600
Mikroprogramowanie, potokowanie Rozbudowany SO TI-ASC
Praca interaktywna PDP-8
Czwarte Układy scalone (LSI oraz VLSI) Wieloprocesorowość VAX 9000
1975-1990 Pamięci półprzewodnikowe Języki Ada, Modula Cray X-MP
Superkomputery wektorowe Środowisko dla pracy równoległej IBM 3090
Piąte Układy scalone (ULSI) Język Java. WWW. Cray MPP
1991-..... Architektura skalowalna Przetwarzanie równoległe Intel Paragan
VPP500
y
ródło: M. Hajder i inni  Informatyka.Wirtualna podró\
w świat systemów i sieci komputerowych
Cechy współczesnych systemów
komputerowych
Systemem komputerowym nazywamy zbiór wzajemnie
powiązanych wzajemnie elementów (komputer,
urządzenia peryferyjne, oprogramowanie) których
współdziałanie pozwala osiągnąć zadany cel
" Wielofunkcyjność  przystosowanie do realizacji
ró\
norodnych zadań (uniwersalność)
" Zło\
oność  wysoki stopień skomplikowania sprzętu i
oprogramowania
" Hierarchiczność  podział na etapy, umo\
liwia rozbicie
przetwarzania
" Spójność  systemu nie da się rozbić na niezale\
ne
funkcjonalne elementy
" Rozproszenie  informacja przetwarzana w ró\
nych
miejscach (tam gdzie powstaje)
Cechy współczesnych systemów
komputerowych
" Zmienność struktury  mo\
liwość dostosowania
systemu do zadania
" Niezawodność  bezawaryjność, mo\
liwość
odtworzenia danych w razie uszkodzenia
" Kontrola i diagnostyka  dostępność narzędzi
diagnostycznych
" Niejednorodność  ró\
norodność w działaniu
(nie przeszkadzająca we współpracy)
" Równoległość  mo\
liwość jednoczesnej pracy
wielu elementów przetwarzających
" Otwartość systemu  mo\
liwość jego rozbudowy
" Moc obliczeniowa