Matematické Fórum

Spasitel · 13. 04. 2009 10:13

Zdravím,

snažím se vyřešit následující příklad, jenže aboslutně nemám tušení jak s tím začít, napadá mě aspoň částečně, jak by to mohlo jít, ale jelikož to jsou jakákoliv 2 binarní čísla, tak vše co mě napadá se jeví, jako totální nesmysl s mnoha a mnoha stavy. Předpokládám, že na to bude nějaká jednoduchá finta, nebo algoritmus. Takže pokud by někdo věděl, jak na to, tak bych byl moc rád.

Díky

Zadání:
Navrhněte jednopáskový Turingův stroj pro násobení binárně zapsaných čísel.
Vstupem stroje bude dvojice binárních čísel zapsaná na pásce. Po skončení výpočtu zůstane
na pásce jejich součin (zapsaný binárně).

Wotton · 01. 02. 2010 14:25

Vím, že odpověď na tento příspěvek už asi nemá moc smysl. Autor už to nejspíš dávno vyřešil, nebo kvůli nevyřešení byl odejit ze svého ústavu. Ale když mně Turingovy stropje baví, a vaníc když si dobrá duše stěžuje že je moc nezodpovězených dotazů, a tímhle zodpovím hned 2:-)

Předpokládám, že na pásce jsou právě 2 čísla. Začátek je na nejlevějším znaku prvního (levého) z nich. Program jsem si omezil na zákaz používání pomocných symbolů, ale na druhou stranu jsem si povolil zápis nalevo od vstupu (což se někdy nepovoluje). Na konci výpočtu zůstane na pásce jediné slovo (součin původních čísel), a program skončí na prvním znaku. Mezeru značím tečkou.

A jsem zvědav, jestli to po mně někdo bude kontrolovat:-)

musixx · 01. 02. 2010 15:13 — Editoval musixx (01. 02. 2010 15:36)

V tom TeXu bude buď nějaká chyba nebo je možná jen příliš dlouhý - nezobrazuje se mi. Ale podle textů kolem předpokládám, že bylo napsáno něco "úsporného", v zásadě násobička.

Turignovy stroje jsou ale spíše nástroj teoretický. Takže bych se nebál neefektivního algoritmu. Klidně bych použil stroj s několika páskama. Na jedné je první činitel v binární podobě, na druhé druhý činitel. Pak bych dal další dvě pásky, kam si převedu tyto dva vstupy do unární podoby (pomocí další pásky, na které si pamatuju vždy konkrétní mocninu dvojky). Tato unární čísla snadno unárně vynásobím na další pásku a výsledek převedu do binární podoby (opět pomocí pásky s mocninou dvojky) na poslední pásku.

Stavy takového stroje potom v zásadě budou odpovídat funkcím, (resp. pásky proměnným), pokud bych to programoval v nějakém vyšším programovacím jazyku (kde bych nejspíš místo unární pomocné soustavy použil desítkovou).

EDIT: Výhodu tohoto přístupu vidím hlavně v tom, že výsledný popis stroje bude přehledný a snadno čitelný.

Wotton · 01. 02. 2010 15:41

↑ musixx:
Samozřejmě, že by se dal s úspěchem použít výcepáskový stroj. Zvlášť když víme že je co do síly jednopáskovému ekvivalentní, ale když v zadání byl stroj jednopáskový, tak se to nedá moc obcházet.

Jen trochu pochybuju o smysluplnosti takového úkolu pro studenty. Myslím, že pro pochopení princilu bohatě stačí najít rozhodovací algoritmus, nebo algoritmus na sčítání, ... tohle už je trochu zbytečný.

Matematické Fórum

#1 13. 04. 2009 10:13

Návrh Turingova Stroje pro násobení binárních čísel

#2 01. 02. 2010 14:25

Re: Návrh Turingova Stroje pro násobení binárních čísel

#3 01. 02. 2010 15:13 — Editoval musixx (01. 02. 2010 15:36)

Re: Návrh Turingova Stroje pro násobení binárních čísel

#4 01. 02. 2010 15:41

Re: Návrh Turingova Stroje pro násobení binárních čísel

Zápatí