Математическая теория формальных языков
Алгоритмические проблемы
Основная цель этой лекции - дать определения понятий, необходимых для математически строгой формулировки результатов следующих двух лекций. Для более подробного ознакомления с вычислимостью, разрешимостью, перечислимостью и универсальными моделями вычислений следует обратиться к какому-либо вводному курсу по теории алгоритмов, например [30, с. 93-106, 109-121]
или [5,с. 8-20, 112-123].
В разделе 14.1 фиксируется конкретная модель вычислений - машина Тьюринга и даются определения (недетерминированной) машины Тьюринга, детерминированной машины Тьюринга и вычислимой функции. В разделе 14.2 определяются разрешимые и перечислимые множества. В разделе 14.3 вводятся термины "массовая задача", "индивидуальная задача", "схема кодирования", "задача распознавания", "алгоритмическая проблема". В 14.4* формулируется теорема о соответствии машин Тьюринга грамматикам типа 0, а также теорема о нормальной форме для грамматик типа 0. В разделе 14.5 формулируется известная неразрешимая проблема - проблема соответствий Поста. На сведEнии именно к этой алгоритмической проблеме основываются все доказательства неразрешимости в лекции 16, где рассматриваются алгоритмические проблемы, связанные с контекстно-свободными грамматиками.
