машины Тьюринга

  • Босс В. Лекции по математике. Т. 6: От Диофанта до Тьюринга. – М.: КомКнига, 2006. – 208 с.
    Книга посвящена основаниям математики, проблемам вычислимости и доказуемости. Машины Тьюринга, рекурсивные функции, логика, теория моделей, неразрешимость и неаксиоматизируемость арифметики, десятая проблема Гильберта — вот рассматриваемый круг вопросов. Изложение отличается краткостью и прозрачностью. Значительное внимание уделяется мотивации результатов и прикладным аспектам.