1. Синтаксис языка лисп. Списки. Атомы. Виды атомов. Комментарии

9. Расширения машины Тьюринга

1. 
   Однонаправленная (односторонняя) МТ – с лентой, ограниченной только с одной стороны.
   
2. 
   Многоленточная МТ – на каждой ленте своя головка, в правилах присутствуют условия и действия для всех лент сразу. Эквивалентна ДМТ. q₁a₁b₁c₁ → q₂a₂b₂c₂D_aD_bD_с
   
3. 
   Недетерминированная МТ. Если существует пара «ленточный символ — состояние», для которой существует 2 и более команд, такая машина Тьюринга называется недетерминированной. Эквивалентна ДМТ. [выполняет N шагов, когда ДМТ потребуется c×e^N]
   
4. 
   Рандомизированная МТ – двухленточная МТ, одна из лент которой заполнена случайными числами (например, нулями и единицами). Некоторые алгоритмы работают медленнее, но некоторые — быстрее, например быстрая сортировка (со случайным выбором пропорции разбиения она стабильнее)
   

10. Примитивно рекурсивные функции Чёрча

• 
  Число 0
  
• 
  Инкремент f(x)=x+1
  
• 
  Функция проекции f(x₁, …, x_n) = x_k
  

• 
  Суперпозиция: ₁, …, g_m> = f(g₁, …, g _m)
  

• 
  Оператор примитивной рекурсиии =
  
  • 
    
    
  • 
    
    

• 
  Функция сложения:
  

• 
  Функция умножения:
  

• 
  Степень:
  

• 
  Декремент:
  

• 
  Вычитание:
  

• 
  Модуль разности:
  

• 
  Знак числа (на самом деле – ноль/не ноль):
  

• 
  Минимум: