2015-02-18
251
[1] Степанов А.Н. Информатика: Учебник для вузов. 4-е изд. – СПб.: Питер, 2005. – С. 41.
[2] Этой теории будут посвящены следующие лекции.
[3] В теории нормальных алгорифмов пустое слово обозначается символом l.
[4] b – подслово слова a.
[5] В ряде источников, например в [], стандартным считается то положение, при котором головка «обозревает» ячейку, в которой записана первая буква слова, т.е. крайне левую ячейку.
[6] Здесь и далее в соответствии с тезисами теории алгоритмов под вычислимыми функциями подразумеваются частично рекурсивные функции. Соответственно под всюду определенными вычислимыми функциями – общерекурсивные функции.
[7] Эти программы могут, например, располагаться в порядке возрастания их длины.
[8] Если в классе А отсутствует нигде не определенная функция, то можно взять произвольную функцию из класса А, а нигде не определенную функцию из его дополнения.
[9] Не тривиальным в том плане, что класс всех вычислимых функций разбивается на два непустых подкласса функций, обладающих и не обладающих этим свойством.
