pomocy z Turingiem

[RoX97]

Witam, zna może ktoś rozwiazanie poniższego?... bo chyba jakiś wykład opuściłem a w piątek egzamin...
rysunki mojego autorstwa więc coś mogłem spaprac...
ok...

zadanie 1 wyglada tak...:

Maszyna Turinga ma na taśmie następujący siąg symboli: ##1101## i diagram przejść (załącznik):

Co będzie zapisane na taśmie w chwili zatrzymania sie maszyny, jeśli głowica jest ustawiona na pierwszym z lewej symbolu nie #?

ja będe strzelał, że ##0010## jeśli dobrze zgaduje o co w tym chodzi

[RoX97]

i jeszcze jedno zadanie:

Maszyna Turinga ma na taśmie następujący siąg symboli: ##0011## i diagram przejść (załącznik):

Co będzie zapisane na taśmie w chwili zatrzymania sie maszyny, jeśli głowica jest ustawiona na pierwszym z lewej symbolu nie #?

a tu chyba będzie wynik wejściowy, ale niemam pojęcia czy dobrze myśle... a moze same #######... ehh...

wolał bym nie rozwiązanie a jakiś opis w miare normalny opis działania takiej maszynki... za wszelka pomoc z wielkie dzięki

[pawelblu]

Ad1. ##0010## (dolna lub gorna czesc schamtu pomyliles - ma byc 0/1/-&gt - tak mi sie wydaje
Ad2. ##0011## jak dojdzie do drugiej kropki bedzie ##1100## i znacznik na drugim zerze, znowu zacznie zamieniac, znacznik bedzie sie cofal i otrzymamy wlasnie ##0011## - znowu pomylka w pierszej czesci diagramu 0/1/->. Maszyne Turinga mialem w tym semestrze (wspomniana) i szczerze mowiac nie mam z tego notatek i tego za bardzo nie pamietam - ale to wydaje mi sie logiczne (a/b/c) a-na czym stoi znacznik b-co ma wstawic c-w ktora strone ma sie przesunac
# o ile pamietam to znak specjalny mowiacy o bodajrze koncu wyrazu

[RoX97]

Wielkie dzieki!
faktycznie pomylilem sie w pierwszej czesci diagramu,
# - wartosc pusta (null) -> czyli chyba tez znacznik konca wyrazu

[RoX97]

mam jeszcze jedno pytanie, wlasciwie to mam sporo, ale na reszte znajde odpowiedz do jutra a do tego niewiem jak sie zabrac...
mianowicie:

Zlozonosc praktyczna algorytmu wynosi: 2^n-n^3+n.
Jaka jest zlozonosc teoretyczna?

czy zlozonosc praktyczna moze byc rowna teoretycznej, czy zwyczajnie bedzie to n^2?

--------------
uaktualnienie:

juz sie doszukalem
tu bedzie 2^n, reszte mozna sobie darowec -> w miare wzrostu n znaczenie reszty czynnikow (n) bedzie malalo wzgledem pierwszego,
czyli powinno to dazyc w strone 2^n.