– За проблем с решение P се казва, че е полурешим (т.е. има полуалгоритъм), ако езикът L на всички екземпляри с „да“към P е r.e. – (Проблем с еквивалентността за DFA) Като се имат предвид два DFA, приемат ли един и същ език? Доказателство: Припомнете си аргумента на Кантор от Първа лекция.
Кога се каже, че проблемът е полурешим?
Полурешими проблеми са тези за които машина на Тюринг спира на входа, приет от нея, но може или да спре, или да се завърти завинаги на входа, който е отхвърлен от машината на Тюринг. Такива проблеми се наричат проблеми, разпознаваеми по Тюринг.
Какво е частично разрешим проблем?
Определение: Един чийто асоцииран език е рекурсивно изброим език. Еквивалентно съществува алгоритъм, който спира и извежда 1 за всеки екземпляр с отговор "да", но за случаи с отговор "не" е позволено или да не спира, или да спре и да изведе 0.
Разрешим ли е частично проблемът със спирането?
Алан Тюринг доказа през 1936 г., че общ алгоритъм, работещ на машина на Тюринг, който решава проблема със спирането за всички възможни двойки програма-вход, непременно не може да съществува. Следователно проблемът за спиране е нерешим за машините на Тюринг.
Защо проблемът със спирането е полурешим?
Език се казва, че е полуразрешим, ако съществува машина на Тюринг, която спира, ако дадена дума принадлежи на езика (случаи ДА) и може да отхвърли или да отиде в безкрайност цикъл, ако думата не принадлежи на езика (БЕЗ регистр).
