turing zdziwiony: Maszyna Turinga OK, mieliśmy dzisiaj o niej na wykładzie i szczerze mówiąc NIC nie rozumiem. Nie było żadnych algorytmów, jakiś film, że da się ją zbudować z klocków lego, info, że ma iglicę, taśmę itp. a potem, że jest wirtualna. Większość stron to bełkot. Może mi ktoś polecić źródło albo napisać tutaj o co tak właściwie chodzi?

zdziwiony: w ogóle czułem się jakbym czytał Lema, gość plótł, że jest cudoffna, uniwersalna, że to taki jakby mózg ludzki. BOMBA

Dziadek Mróz: Maszyna turinga działa na tej zasadzie, że istnieje taśma z bitami danych. Instrukcjami w programie sterujesz ruchem głowicy po taśmie. Kiedyś mieliśmy taki prosty program do nauki. Dla przykładowej taśmy, głowica na pierwszym zajętym bicie, # jest puste: #11110111# ^ 111₁ + 111₁ mamy program dodający dwie liczby w systemie unarnym oddzielone zerem, gdzie pierwsza będzie o 1 większa: 1. A, 0; A, 1, > 2. A, 1; A, 1, > 3. A, #; B, #, < 4. B, 1; C, #, < 5. C, 1; D, #, > Instrukcje czyta się tak: typ głowicy wej., co napotkano; typ głowicy wyj., co zapisano, kierunek ruchu głowicy A, 0; A, 1, > wej. A, napotkane 0; wyj. A, zapisano 1, w prawo Kierunkiem głowicy może być także numer instrukcji w programie #11110111# : A[1] → A, 1; A, 1, > #11110111# : A[1] → A, 1; A, 1, > #11110111# : A[1] → A, 1; A, 1, > #11110111# : A[1] → A, 1; A, 1, > #11110111# : A[0] → A, 0; A, 1, > #11111111# : A[0] → A, 1; A, 1, > #11111111# : A[0] → A, 1; A, 1, > #11111111# : A[0] → A, 1; A, 1, > #11111111# : A[#] → A, #; B, #, < zmiana głowicy z A na B #11111111# : B[1] → B, 1; C, #, < zmiana głowicy z B na C #1111111## : C[1] → C, 1; D, #, > zmiana głowicy z C na D #111111### : D[#] → brak instrukcji dla D[#], koniec 111₁ = 1*1⁰ + 1*1¹ + 1*1² = 1 + 1 + 1 = 3₁₀ 111₁ = 1*1⁰ + 1*1¹ + 1*1² = 1 + 1 + 1 = 3₁₀ 111₁ + 111₁ = 3₁₀ + 3₁₀ = 6₁₀ = 111111₁

zdziwiony: Dobrze, bardzo Ci dziękuję. A czy mógłbyś jeszcze napisać dlaczego ta maszyna jest taka wspaniała? Kodem binarnym posługiwał się już Leibniz a i kilku wcześniej, nie widzę tej rewolucyjności. I jak ta maszyna miałaby rozwiązać skomplikowany szyfr/algorytm skoro wszystkie działania są przez nas zaprogramowane?

Dziadek Mróz: Bo maszyna nie musi tylko na binarnym się opierać, może znajdować jakieś wzorce znaków, usuwać znaki z taśmy, bloki znaków. Praktycznie tą maszyną możesz dowolnie operować na danych.