Литература по вычислимым функциям

Чтобы проникнуться темой вычислимых функций, можно по крайней мере почитать 3 книжецы на русском:
  —  Верещагин Н. К., Шень А., Вычислимые функции;
  —  Хопкрофт Д., Мотвани Р., Ульман Дж., Введение в теорию автоматов, языков и вычислений;
  —  Андреева Е. В., Босова Л. Л., Фалина И. Н., Математические основы информатики.

Книги приведены в порядке убывания сложности. В первой описано все слишком абстрактно, хорошо с точки зрения математики, во второй  — более понятно простому смертному, ну а третья — для школоты. Если «Вычислимые функции» не целый курс, то можно воспользоваться именно третьей книжицей, очень коротко, но необходимое есть.

Да, можно почитать Сипсера (M. Sipser, Introduction to the Theory of computation), но он на англ., и тема вычислимых функций не в первой главе, поэому нужно будет «пролистать» еще полкниги.
Но судя по теме конечных автоматов написано очень доступно.