Привет! Сегодня я хочу обзорно пройтись по нескольким задачам времен рассвета информатики aka Сomputer Science, которые относятся к неразрешимым.
Что такое неразрешимая задача? Наверное, стоило бы начать с иерархии Хомского — регулярные, контекстно-свободные, контекстно-зависимые, рекурсивно-перечислимые языки, — а уже потом перейти к тому, что лежит за её пределами, но, честно, это не слишком весело. Я не буду давать ни формальных определений, ни доказательств. У вас не получится поддержать научный диспут, но ввернуть умную фразу в компании — вполне. Если вас это устраивает — прошу под кат.
Читать полностью »
