Bináris szorzás turing géppel?

Egy lehetséges megoldás:

Input: x, y

Output: x + y

Bonyolultság: exptime

Az első szalagon tárolod az x-et, a másodikon az y-t, a harmadikon az outputot, ami az elején 0. Minden ciklusban hozzáadod az outputhoz az y-t és 1-gyel csökkented az x-et és ezt addig csinálod, amíg az x nem lesz 0.

Ha polinom idejű algoritmus kell, akkor az írásos szorzást kell megvalósítani.