Maszyna turinga

pytanie zadane 22 kwietnia 2019 w Inne języki przez piotr99511 Nowicjusz (120 p.)

Witam!

Zacznijmy od tego, że studiuję informatykę. Na jednym z przedmiotów dostałem za zadanie zaprojektowanie maszyny turinga. Maszyna ta ma za zadanie realizacje zadania: dla danej zawartości taśmy przykładowo: b010010b mam wstawić w jej środek b. Gdzie b jak się domyślam jest to stan niezdefiniowany. Maszyna może działań na wielu taśmach. Nie mam pomysłu od czego w ogóle zacząć. Samą idee maszyny rozumiem aczkolwiek nie umiem tego zaprojektować. Z góry dziękuje za wszelkie wskazówki!

komentarz 22 kwietnia 2019 przez Ajver Bywalec (2,430 p.)

Jeśli taśma ma taką zawartość: b010010b człowiek szybko dostrzeże tu wzór. Czy fakt, że zawartość tej taśmy można podzielić na dwie symetryczne części jest przypadkowe? Czy to, że b ma być na środku wynika z tego, że jest po jednym b na każdym krańcu? Pytam, bo nie wiem, czy ta maszyna zawsze wstawia b na środku, czy określa pozycję nowego b na podstawie obecnej zawartości taśmy?

komentarz 22 kwietnia 2019 przez piotr99511 Nowicjusz (120 p.)

Z tego co zrozumiałem ma wstawić b w taki sposób, że otrzymamy b010b010b. I wydaje mi się, że trzeba będzie to zapisać na oddzielnej taśmie.

1 odpowiedź

odpowiedź 22 kwietnia 2019 przez Aisekai Nałogowiec (42,190 p.)
przywrócone 22 kwietnia 2019 przez Aisekai

Nie dam Ci rozwiazania, ale ja bym podszedł do tego w ten sposób:

"zapamietalbym" to co znajduje się jako pierwszy symbol na taśmie z lewej strony i zastąpił bym go 'b'. Przeszedł bym na koniec, zapamietalbym to co jest na końcu i zastąpił koniec b. Wrócił bym na początek wstawił zapamietany symbol w miejsce b przeszedł w prawo i wstawił b. Potem na koniec, wstawił zapamietany z końca w miejsce b, w lewo i wstawił b. Do tej pory bym to robil, az przy przechodzeniu głowicy na początek/koniec nie napotkal dwóch b obok siebie. Możliwe, że da się to zrobić lepiej ale tobpierwszy pomysł co mi do głowy wpadł.

komentarz 22 kwietnia 2019 przez Ajver Bywalec (2,430 p.)

A czy nie prościej użyć zwykłych tablic, których rozmiar znasz? W C++ np. Można użyć kontenera stl vector. Można wcisnąć b w dowolne miejsce, w które chcesz. W językach wyższego poziomu wystarczy do tego zwykła tablica.

Ewentualnie możesz zrobić coś takiego, żeby połowę tablicy przesunąć o jedną komórkę dalej a na jej środek dac b.

komentarz 22 kwietnia 2019 przez Aisekai Nałogowiec (42,190 p.)

Problem jest taki, że zadanie dotyczy Maszyny Turinga a nie jakiegoś języka programowania. Mówiąc zapamietalbym miałem na myśli dodatkowe stany które by to reprezentowały.

https://pl.m.wikipedia.org/wiki/Maszyna_Turinga

komentarz 23 kwietnia 2019 przez piotr99511 Nowicjusz (120 p.)

@Aisekai, analizując Twój pomysł doszedłem do etapu końcowego. Jeśli wszystko zrobiłem jak należy to uzyskałem rozdzielony na pół "ciąg" oddzielony przez bb a w treści zadania była mowa o oddzieleniu pojedynczym znakiem b. Czy może coś zrobiłem źle? A może jest jakiś łatwy sposób na skorygowanie błędu?

komentarz 23 kwietnia 2019 przez piotr99511 Nowicjusz (120 p.)

Jeszcze jedno pytanie. W jaki sposób mam dokonać przesunięcia "na koniec" / "na początek". W jedno taśmowej maszynie turinga mogę przesuwać się wyłączne o jedną pozycję :/

komentarz 23 kwietnia 2019 przez Aisekai Nałogowiec (42,190 p.)

W chwili, gdy będziesz miał dwa "bb" obok siebie, to wystarczy, że uzupelnisz jedno z tych "b" tym za co wcześniej wstawiles "b".

No tak, przy czym.w maszynie turinga masz stany więc, mając głowice ustawioną po lewej stronie, przesuwasz się w prawo do czasu, aż nie napotkasz "b". Napotykając "b" wiesz, że glowica jest na końcu Analogicznie w drugą stronę.

komentarz 23 kwietnia 2019 przez piotr99511 Nowicjusz (120 p.)

Jeżeli tak zrobię to wyjdzie mi inny "ciąg" niż początkowo.

komentarz 23 kwietnia 2019 przez Aisekai Nałogowiec (42,190 p.)

Inny, bo z 'b' w środku. Reszta będzie taka sama.

komentarz 23 kwietnia 2019 przez piotr99511 Nowicjusz (120 p.)

Moze napisze jak ja widze etapy:

kolejno:

b010010b

bb1001bb

0b1001b0

0bb00bb0

01b00b10

01bbbb10

010bb010

Do tego momentu jest okay?

I teraz chcąc mieć aby jedno b w środku (według tego co rozumiem)

wcześniej wstawiłem za b -> 0 więc

0100b010 no i nie pasuje ;/