Недетермінована машина Тюрінга: відмінності між версіями
[неперевірена версія] | [перевірена версія] |
Вилучено вміст Додано вміст
мНемає опису редагування |
м →Приклад: clean up, replaced: представляє собою → являє собою |
||
Рядок 69:
(Алгоритм написаний не безпосередньо у вигляді визначення машини Тьюринга.)
Під час обчислення цього алгоритму визначальною частиною є час виконання ділення, яке може бути виконано за ''[[O большое|O]](b<sup>2</sup>)'' кроків, що
Для реалізації такого часу обчислення, потрібно вдало вибирати число ''m'', або виконувати обчислення по всіх можливих шляхах (для всіх можливих ''m'') одночасно на безлічі копій машини.
|