Question

Согласно тезису Чёрча-Клини:
а) каждая интуитивно вычислимая функция является частично рекурсивной.
б) каждая рекурсивная функция является вычислимой.
в) каждая интуитивно вычислимая функция является частично рекурсивной.
г) каждая интуитивно вычислимая функция является общерекурсивной.

2.Остановка МТ происходит, когда
а) выполнена последняя подстановка
б) в состоянии P0 машина остается на месте
в) не изменяется символ внутреннего алфавита
г) не изменяется символ внешнего алфавита, состояние МТ остается неизменным, сдвиг – нулевой

3.Команда машины Тьюринга состоит из
а) символа внешнего алфавита, символа внутреннего алфавита, сдвига
б) подстроки P, символа→, строки Q
в) номера состояния ленты МТ, символа алфавита и сдвига
г) номера команды, знака команды, номера следующей команды

4. Если алгоритм имеет экспоненциальную сложность то
а) при увеличении N можем не получить решение задачи физически, т.к. это займёт очень много времени.
б) имеет место значительное