Почему надо «знать» машину Тьюринга – решение задачи
(тест для программистов и работающих рядом с ними).

 Как написать программу, которая будет способна декодировать текст, записанный в произвольной кодировке, и приводить его к «читабельному» виду.

Подсказка, которая была дана, проста, но достаточна для решения задачи: подумайте, чем занимается, какие исследования ведет Институт русского языка Академии наук.

Тематика исследований, наверняка, обширна. Для нас же существенно, что одним из направлений деятельности института является составление частотных словарей классиков русской литературы.

Что такое частотный словарь? Это словарь наиболее часто используемых слов и выражений. Частотный словарь писателя позволяет проследить, как происходит с годами эволюция используемого автором языка. Когда появляются новые слова и выражения, когда перестают использоваться устаревшие выражения и обороты.
В практическом плане это позволяет определить, примерно, дату написания произведений, для которых нет точной датировки. Кроме того, это позволяет определить,  является ли классик автором произведения, авторство которого не установлено, но есть основание полагать, что он его написал.
Естественно, что сотрудники Института русского языка не обошли своим вниманием и русский язык как единое целое. Существует частотный словарь слов русского языка и частотный словарь букв русского языка.
Именно частотный словарь букв русского языка нам и нужен. Проведем анализ закодированного текста и определим какой код встречается чаще всего. Если текст, который нам нужно прочесть, действительно закодированный текст, написанный на русском языке, то все, что нам надо сделать – это поставить в соответствие этому коду наиболее часто встречающуюся букву русского языка. Коды остальных букв вычисляются автоматически. Можно построить таблицу перекодировки.

Попробуйте угадать, какая из букв русского языка встречается чаще всего?
Буква О
. Частота появления – 0.090. Т.е. в последовательности из 1000 букв, буква О будет встречаться в среднем 90 раз.
Какие буквы занимают лидирующие позиции, встречаются чаще всего?
Гласные.
Именно они чаще всего встречаются в русском языке, делаю нашу речь «певучей». Следом за О идут буквы Е и Ё (вместе, их не разделяют, т.к. при написании, часто теряют Ё). Частота появления – 0.072. За ними – буквы А и И. Частота появления каждой из них – 0.062.
Достаточно ли этого для того, чтобы декодировать текст?
В принципе да, если мы уверены, что последовательность кодов содержит текст именно на русском языке в какой-то из известных или неизвестных нам кодировок. Но всегда есть некоторая вероятность, что предъявленная последовательность кодов никакого отношения к русскому языку не имеет. Чтобы убедиться в этом, надо воспользоваться частотным словарем слов русского языка.

Как вы полагаете, какое слово встречается в русском языке чаще всего?
Союз И, затем следуют столь же краткие части речи – В, НЕ, ОН, НА. Но чаще всего, конечно, будет встречаться пробел.
Декодируемый текст надо проверить на совпадение по частотному словарю. И только при более-менее полном совпадении можно говорить о том, что мы имеем дело текстом, написанном на русском языке.
Это дает 100% результат, если текст достаточно большой. Если же речь идет о нескольких словах, то частота букв (и тем более слов) может быть нарушена. Что делать в этом случае? Надо предложить читателю несколько вариантов на выбор. Декодировать текст по одной из гласных букв, которые встречаются чаще всего. Гласные! Они всегда будут встречаться чаще других букв. Если закодирован именно текст на русском языке, то успех гарантирован.

Могут, конечно, возникнуть некоторые технические трудности, связанные переключением регистра или буква может кодироваться двумя байтами, а не одним, но это не принципиально.