Машина Поста и машина Тьюринга

Министерство  образования и науки РФ Федерального государственное бюджетное образовательное  учреждение Высшего профессионального  образования « Шуйский Государственный  Педагогический Университет»

 

 

 

 

 

Реферат по информатике.

Кафедра Информационных систем и технологий

Тема: «Машина  Поста и машина Тьюринга»

 

 

 

 

 

 

 

 

 

 

Работу  выполнила студентка ТФ 1-2

Гонохина  Екатерина Андреевна

Работу  проверила:  Голубева Светлана Константиновна

 

 

 

 

 

2012 год.

Содержание:

 

1. Машина Поста…………………………………………. 3
1. Введение…………………………………………....
2. Принцип работы…………………………………..
3. Объекты используемые в программе…………..
4. Функции используемые в программе…………..
5. Варианты окончания выполнения программы на машине Поста…………………………………………………...
6. Пример работы машины Поста…………………

 

2. Машина Тьюринга…………………………………….. 9
1. Введение…………………………………………….
2. Описание машины Тьюринга…………………....
3. Свойства машины Тьюринга как алгоритма….
4. Сложность алгоритмов……………………………
5. Сложность проблем………………………………..
6. Машина Тьюринга и алгоритмически неразрешимые проблеммы…………………………………….
7. Заключение…………………………………………
8. Пример работы машины Тьюринга…………….

 

 

            3.        Список используемой  литературы……………………......20

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1 Машина Поста 

 

       1.1 Введение

Машина Поста – это абстрактная (несуществующая реально) вычислительная машина, созданная для уточнения (формализации) понятия алгоритма. Представляет собой универсальный исполнитель, позволяющий вводить начальные данные и читать результат выполнения программы. 
В 1936 г. американский математик Эмиль Пост в статье описал систему, обладающую алгоритмической простотой и способную определять, является ли та или иная задача алгоритмически разрешимой. Если задача имеет алгоритмическое решение, то она представима в форме команд для машины Поста.

 

1.2 Принцип работы

Машина  Поста состоит из каретки (или  считывающей и записывающей головки) и разбитой на секции бесконечной  в обе стороны ленты. Каждая секция ленты может быть либо пустой — 0, либо помеченной меткой 1. За один шаг  каретка может сдвинуться на одну позицию влево или вправо, считать, поставить или стереть символ в том месте, где она стоит. Работа машины Поста определяется программой, состоящей из конечного числа  строк. Всего команд шесть: N. → J сдвиг вправо N. ← J сдвиг влево N. 1 J запись метки N. 0 J удаление метки N.  ? J1, J0 если в ячейке 1, то перейти к j1 строке программы, иначе перейти к j0 строке. N. Stop остановка

N. — номер  строки, J — строка на которую  переходит управление далее.

Для работы машины нужно задать программу  и ее начальное состояние (т. е. состояние  ленты и позицию каретки). После  запуска возможны варианты: работа может закончиться невыполнимой командой (стирание несуществующей метки  или запись в помеченное поле); работа может закончиться командой Stop; работа никогда не закончится.

1.3 Объекты используемые  в программе

• Memo-это текстовое поле с возможностью построчного считывания и зиписи. Используется для исходного текста программы и для демонстрации интерпетированного кода в его пошаговом исполнении.
• Edit- это текстовое поле с возможностью считывания и зиписи, в полях этого типа храняться: исходная лента машины Поста, ее текущее состояние, и информация о работе программы
• Button- кнопки, запускает определенные наборы функций и команд к выполнению

 

1.4 Функции используемые  в программе

• Char shag(void) Обработка одной текущей команды машины Поста. Сдвигает каретку, снимает или ставит метку, осуществляет условный переход. Возвращает код ошибки: 0-нет ошибки -1-переход на команду меньше нуля -2 попытка перехода на команду больше максимального числа команд -3 попытка снять метку где ее нет -4 попытка установить метку где она есть Если получает символ остановки "S" то возвращает 0, по командам не сдвигается
• void print_sostoyanie(int i) отображает состояние машины поста(Memo2), включая текушую команду(показана "*"), текущее состояние ленты с позицией каретки(Edit2), а также результаты выполнения последней команды(Edit4) и показывает нормальное завершение программы на языке машины поста. i-тип результата последней команды. Если i=: 1- начальное состояние(произведена инициализация и не одной команды не выполнилось) -2 попытка перехода на команду больше максимального числа команд -3 попытка снять метку где ее нет -4 попытка установить метку где она есть 0 программа выполняется
• void fastcall TForm1::Button1Click(TObject *Sender) Обработчик нажатия кнопки "c начала". Производит полный разбор и инициализацию данных (позиция каретки, создает массив данных ленты,получает массив команд во внутреннем представлении из текста). Запускает функцию print_sostoyanie(1)
• voidfastcall TForm1::Button2Click(TObject *Sender) Выполнение одного шага и обновление данных, вызывает функции:shag, print_sostoyanie.
• void fastcall TForm1::Button3Click(TObject *Sender) Выполняет m шагов начиная с последнего, количество выполняемых при нажании этой кнопки шагов берется из Edit3. Обновляются данные на формах принт начала программы

 

Машина Поста состоит из:

• бесконечной ленты, поделенной на одинаковые ячейки (секции). Ячейка может быть пустой (0 или пустота) или содержать метку (1 или любой другой знак),
• головки (каретки), способной передвигаться по ленте на одну ячейку в ту или иную сторону, а также способной проверять наличие метки, стирать и записывать метку.

Текущее состояние машины Поста описывается состоянием ленты и положением каретки. Состояние ленты – информация о том, какие секции пусты, а какие отмечены. Шаг – это движение каретки на одну ячейку влево или вправо. Состояние ленты может изменяться в процессе выполнения программы.

Кареткой управляет программа, состоящая из строк команд. Каждая команда имеет следующий синтаксис:i K j,

где i - номер команды, K – действие каретки, j - номер следующей команды (отсылка).

Всего для  машины Поста существует шесть типов  команд:

1. V j - поставить метку, перейти к j-й строке программы.
2. X j - стереть метку, перейти к j-й строке программы.
3. <- j - сдвинуться влево, перейти к j-й строке программы.
4. -> j - сдвинуться вправо, перейти к j-й строке программы.
5. ? j₁; j₂ - если в ячейке нет метки, то перейти к j₁-й строке программы, иначе перейти к j₂-й строке программы.
6. ! – конец программы (стоп).

У команды «стоп» отсылки нет.

1.5 Варианты окончания выполнения  программы на машине Поста:

1. Команда "стоп" - корректная остановка. Возникает в результате выполнения правильно написанного алгоритма.
2. Выполнение недопустимой команды – нерезультативная остановка. Случаи, когда головка должна записать метку там, где она уже есть, или стереть метку там, где ее нет, являются аварийными (недопустимыми).
3. Уход в бесконечность, зацикливание. Машина Поста в результате работы алгоритма может вообще не остановиться (никогда не дойти до команды «стоп» и никогда не завершиться аварийной ситуацией).

Элементарные действия (команды) машина Поста проще команд машины Тьюринга. Поэтому программы для машины Поста имеют большее число  команд, чем аналогичные программы  для машины Тьюринга. 
Почему достаточно лишь два различных символа (есть метка, нет метки)? Дело в том, что любой алфавит может быть закодирован двумя знаками; в зависимости от алфавита возрастать может только количество двоичных символов в букве алфавита.

       1.6 Пример работы машины Поста:

Задача: увеличить число 3 на единицу (изменить значение в памяти с 3 на 4). 
Целое положительное число на ленте машины Поста представимо идущими подряд метками, которых на одну больше, чем кодируемое число. Это связано с тем, что одна метка обозначает ноль, а уже две – единицу, и т.д. 
Допустим, точно известно, что каретка стоит где-то слева от меток и обозревает пустую ячейку. Тогда программа увеличения числа на единицу может выглядеть так: 
1. -> 2 
2. ? 1;3 
3. <- 4 
4. V 5 
5. ! 
А процесс выполнения может быть таким:

 

 

 

 

 

Алгоритм  для машины Поста:

1. Сдвинуть каретку влево. Перейти к команде 2.
2. Обозревать ячейку. Если в ячейке нет метки - перейти к команде 1. Иначе - к команде 3
3. Сдвинуть каретку вправо. Перейти к команде 4.
4. Записать метку. Перейти к команде 5.
5. Остановиться.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2 Машина Тьюринга

 

2.1 Введение

В 1936 г. Аланом Тьюрингом для уточнения понятия  алгоритма был предложен абстрактный универсальный исполнитель. Его абстрактность заключается в том, что он представляет собой логическую вычислительную конструкцию, а не реальную вычислительную машину. Термин «универсальный исполнитель» говорит о том, что данный исполнитель может имитировать любой другой исполнитель. Например, операции, которые выполняют реальные вычислительные машины можно имитировать на универсальном исполнителе. В последствие, придуманная Тьюрингом вычислительная конструкция была названа машиной Тьюринга. 
Кроме того, предполагается, что универсальный исполнитель должен уметь доказывать существование или отсутствие алгоритма для той или иной задачи.

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

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

В 1947 г. Алан Тьюринг расширил определение, описав "универсальную машину Тьюринга". Позже для решения определенных классов задач была введена ее разновидность, которая позволяла  выполнять не одну задачу, а несколько.

 

2.2 Описание машины Тьюринга

Алан Тьюринг (Turing) в 1936 году опубликовал в трудах Лондонского математического общества статью "О вычислимых числах в  приложении к проблеме разрешения", которая наравне с работами Поста  и Черча лежит в основе современной  теории алгоритмов.

Предыстория создания этой работы связана с формулировкой  Давидом Гильбертом на Международном  математическом конгрессе в Париже в 1900 году неразрешенных математических проблем. Одной из них была задача доказательства непротиворечивости системы  аксиом обычной арифметики, которую  Гильберт в дальнейшем уточнил как "проблему разрешимости" - нахождение общего метода, для определения выполнимости данного высказывания на языке формальной логики.

Статья Тьюринга как раз и давала ответ на эту  проблему - вторая проблема Гильберта  оказалась неразрешимой. Но значение статьи Тьюринга выходило далеко за рамки  той задачи, по поводу которой она  была написана.

Приведем  характеристику этой работы, принадлежащую  Джону Хопкрофту: "Работая над  проблемой Гильберта, Тьюрингу пришлось дать четкое определение самого понятия  метода. Отталкиваясь от интуитивного представления о методе как о  некоем алгоритме, т.е. процедуре, которая  может быть выполнена механически, без творческого вмешательства, он показал, как эту идею можно  воплотить в виде подробной модели вычислительного процесса. Полученная модель вычислений, в которой каждый алгоритм разбивался на последовательность простых, элементарных шагов, и была логической конструкцией, названной  впоследствии машиной Тьюринга".

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

Формально машина Тьюринга может быть описана следующим  образом. Пусть заданы:конечное множество  состояний – Q, в которых может  находиться машина Тьюринга;конечное множество символов ленты – Г;функция  δ (функция переходов или программа), которая задается отображением пары из декартова произведения Q x Г (машина находится в состоянии qi и обозревает символ gi) в тройку декартова произведения Q х Г х {L,R} (машина переходит в  состояние qi, заменяет символ gi на символ gj и передвигается влево или  вправо на один символ ленты) – Q x Г-->Q х Г х {L,R}один символ из Г-->е (пустой);подмножество Σ є Г - -> определяется как подмножество входных символов ленты, причем е  є (Г - Σ);одно из состояний – q0 є Q является начальным состоянием машины.

Решаемая  проблема задается путем записи конечного  количества символов из множества Σ  є Г – Si є Σ на ленту:eS1S2S3S4... ... ... Sne после чего машина переводится  в начальное состояние и головка  устанавливается у самого левого непустого символа (q0,w) –, после чего в соответствии с указанной функцией переходов (qi,Si) - ->(qj,Sk, L или R) машина начинает заменять обозреваемые символы, передвигать головку вправо или влево и переходить в другие состояния, предписанные функций переходов.

Остановка машины происходит в том случае, если для  пары (qi,Si) функция перехода не определена.

Алан Тьюринг  высказал предположение, что любой  алгоритм в интуитивном смысле этого  слова может быть представлен  эквивалентной машиной Тьюринга. Это предположение известно как  тезис Черча–Тьюринга. Каждый компьютер  может моделировать машину Тьюринга (операции перезаписи ячеек, сравнения  и перехода к другой соседней ячейке с учетом изменения состояния  машины). Следовательно, он может моделировать алгоритмы в любом формализме, и из этого тезиса следует, что  все компьютеры (независимо от мощности, архитектуры и т.д.) эквивалентны с точки зрения принципиальной возможности  решения алгоритмических задач.

2.3 Свойства машины Тьюринга как  алгоритма

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

Дискретность. Машина Тьюринга может перейти к (к + 1) - му шагу только после выполнения каждого шага, т.к именно каждый шаг  определяет, каким будет (к + 1) - й  шаг.

Понятность. На каждом шаге в ячейку пишется  символ из алфавита, автомат делает одно движение (Л, П, Н), и машина Тьюринга переходит в одно из описанных  состояний.

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

Результативность. Содержательно результаты каждого  шага и всей последовательности шагов  определены однозначно, следовательно, правильно написанная машина Тьюринга за конечное число шагов перейдет в состояние q0, т.е. за конечное число  шагов будет получен ответ  на вопрос задачи.

Массовость. Каждая машина Тьюринга определена над  всеми допустимыми словами из алфавита, в этом и состоит свойство массовости. Каждая машина Тьюринга предназначена  для решения одного класса задач, т.е. для каждой задачи пишется своя (новая) машина Тьюринга.

 

2.4 Сложность алгоритмов

Сложность алгоритма  определяется вычислительными мощностями, необходимыми для его выполнения. Вычислительная сложность алгоритма  часто измеряется двумя параметрами: Т (временная сложность) и S (пространственная сложность, или требования к памяти). И Т, и S обычно представляются в виде функций от n, где n - это размер входных  данных. (Существую и другие способы  измерения сложности: количество случайных  бит, ширина канала связи, объем данных и т.п.)

Обычно вычислительная сложность алгоритма выражается с помощью нотации "О большого", т. е описывается порядком величины вычислительной сложности. Это просто член разложения функции сложности, быстрее всего растущий с ростом n, все члены низшего порядка  игнорируются. Например, если временная  сложность данного алгоритма  равна 4n2+7n+12, то вычислительная сложность  порядка n2, записываемая как О(n2).

Временная сложность  измеренная таким образом не зависит  от реализации. Не нужно знать ни точное время выполнения различных  инструкций, ни число битов, используемых для представления различных  переменных, ни даже скорость процессора. Один компьютер может быть на 50 процентов  быстрее другого, а у третьего шина данных может быть в два раза шире, но сложность алгоритма, оцененная  по прядку величины, не изменится. Это  не жульничество, при работе с алгоритмами  настолько сложными, как описанные  в этой книге, всем прочим можно пренебречь (с точностью до постоянного множителя) в сравнении со сложностью по порядку  величины.

Эта нотация  позволяет увидеть, как объем  входных данных влияет на требования к времени и объему памяти. Например, если Т= О(n), то удвоение входных данных удвоит и время выполнения алгоритма. Если Т=О(2n), то добавление одного бита к входным данным удвоит время  выполнения алгоритма.

Обычно алгоритмы  классифицируются в соответствии с  их временной или пространственной сложностью. Алгоритм называют постоянным, если его сложность не зависит  от n: 0(1). Алгоритм является линейным, если его временная сложность О(n). Алгоритмы  могут быть квадратичными, кубическими  и т.д. Все эти алгоритмы - полиномиальны, их сложность - О(m), где m - константа. Алгоритмы  с полиномиальной временной сложностью называются алгоритмами с полиномиальным временем

Алгоритмы, сложность которых равна О(tf(n)), где t - константа, большая, чем 1, a f(n) - некоторая  полиномиальная функция от n, называются экспоненциальными. Подмножество экспоненциальных алгоритмов, сложность которых равна  О(сf(n)), где где с - константа, a f(n) возрастает быстрее, чем постоянная, но медленнее, чем линейная функция, называется суперполиномиальным.

В идеале, криптограф хотел бы утверждать, что алгоритм, лучший для взлома спроектированного  алгоритма шифрования, обладает экспоненциальной временной сложностью. На практике, самые сильные утверждения, которые  могут быть сделаны при текущем  состоянии теории вычислительной сложности, имеют форму "все известные  алгоритмы вскрытия данной криптосистемы  обладают суперполиномиальной временной  сложностью". То есть, известные нам  алгоритмы вскрытия обладают суперполиномиальной  временной сложностью, но пока невозможно доказать, что не может быть открыт алгоритм вскрытия с полиномиальной временной сложностью. Развитие теории вычислительной сложности возможно когда-нибудь позволит создать алгоритмы, для которых существование алгоритмов с полиномиальным временем вскрытия может быть исключено с математической точностью.

С ростом n временная  сложность алгоритмов может стать  настолько огромной, что это повлияет на практическую реализуемость алгоритма.

При условии, что единицей времени для нашего компьютера является микросекунда, компьютер  может выполнить постоянный алгоритм за микросекунду, линейный - за секунду, а квадратичный - за 11.6 дня. Выполнение кубического алгоритма потребует 32 тысяч лет, что в принципе реализуемо, компьютер, конструкция которого позволила  бы ему противостоять следующему ледниковому периоду, в конце  концов получил бы решение. Выполнение экспоненциального алгоритма тщетно, независимо от экстраполяции роста  мощи компьютеров, параллельной обработки  или контактов с инопланетным суперразумом.

Взглянем  на проблему вскрытия алгоритма шифрования грубой силой. Временная сложность  такого вскрытия пропорциональна количеству возможных ключей, которое экспоненциально  зависит от длины ключа. Если n - длина  ключа, то сложность вскрытия грубой силой равна 0(2n). Сложность вскрытия грубой силой при 56-битовом ключе  составляет 256, а при 112-битовом ключе - 2112. В первом случае вскрытие возможно, а во втором - нет.

2.5 Сложность проблем

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

Проблемы, которые  можно решить с помощью алгоритмов с полиномиальным временем, называются решаемыми, потому что для разумных входных данных обычно могут быть решены за разумное время. (Точное определение "разумности" зависит от конкретных обстоятельств) Проблемы, которые невозможно решить за полиномиальное время, называются нерешаемыми, потому что вычисление их решений быстро становится невозможным. Нерешаемые проблемы иногда называют трудными. Проблемы, которые могут  быть решены только с помощью суперполиномиальных  алгоритмов, вычислительно нерешаемы, даже при относительно малых значениях n.

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

Задачи можно  разбить на классы в соответствии со сложностью их решения. Вот важнейшие  из них и предполагаемые соотношения  между ними:

P<=NP<=EXPTIME

Находящийся слева класс P включает все задачи, которые можно решить за полиномиальное время. В класс NP входят все задачи, которые можно решить за полиномиальное время только на недетерминированной  машине Тьюринга (это вариант обычной  машины Тьюринга, которая может делать предположения). Такая машина предполагает решение задачи – либо “удачно  угадывая”, либо перебирая все предположения  параллельно – и проверяет  свое предположение за полиномиальное время.

Класс NP включает в себя класс P, поскольку любую  задачу, решаемую за полиномиальное время  на детерминированной (обычной) машине Тьюринга, можно решить и на недетерминированной  за полиномиальное время, просто этап предположения опускается.

Если все  задачи класса NP решаются за полиномиальное время и на детерминированной  машине, то P=NP. Тем не менее, никем  не доказано, что P<>NP (или P=NP). Однако, большинство специалистов, занимающихся теорией сложности, убеждены, что  это классы неравны.

Как ни странно, можно доказать, что некоторые NP-задачи настолько же трудны, что и любая  задача этого класса. Такие задачи называются NP-полными. То есть, если такая  задача решается за полиномиальное время, то P=NP.

Таким образом, для программиста NP-полнота означает полный перебор, причем сложность этого  перебора будет экспоненциальной или  факториальной. Но следует понимать, что не всякий полный перебор имеет  такую сложность. Например, если решать задачи из предыдущего выпуска полным перебором, то сложность полученных алгоритмов будет полиномиальной - O(n2) для задачи про подпоследовательности  и O(n6) для задачи про подматрицы.

Наконец, существует класс задач EXPTIME. Эти задачи решаются за экспоненциальное время. В настоящее  время можно доказать, что EXPTIME-полные задачи невозможно решить за детерминированное  полиномиальное время. Кроме того, доказано, что P<>EXPTIME.

 

2.6 Машина Тьюринга и алгоритмически  неразрешимые проблемы

За время  своего существования человечество придумало множество алгоритмов для решения разнообразных практических и научных проблем. Зададимся  вопросом – а существуют ли какие-нибудь проблемы, для которых невозможно придумать алгоритмы их решения?

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

Успехи математики к концу XIX века привели к формированию мнения, которое выразил Д. Гильберт – "в математике не может быть неразрешимых проблем", в связи  с этим формулировка проблем Гильбертом на конгрессе 1900 года в Париже была руководством к действию, констатацией отсутствия решений в данный момент.

Первой фундаментальной  теоретической работой, связанной  с доказательством алгоритмической  неразрешимости, была работа Курта  Гёделя – его известная теорема  о неполноте символических логик. Это была строго формулированная  математическая проблема, для которой  не существует решающего ее алгоритма. Усилиями различных исследователей список алгоритмически неразрешимых проблем  был значительно расширен. Сегодня  принято при доказательстве алгоритмической  неразрешимости некоторой задачи сводить  ее к ставшей классической задаче – "задаче останова".

Имеет место  быть следующая теорема: не существует алгоритма (машины Тьюринга), позволяющего по описанию произвольного алгоритма  и его исходных данных (и алгоритм и данные заданы символами на ленте  машины Тьюринга) определить, останавливается  ли этот алгоритм на этих данных или  работает бесконечно.

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

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

а) Отсутствие общего метода решения задачи

Проблема 1: Распределение девяток в записи числа;

Определим функцию f(n) = i, где n – количество девяток  подряд в десятичной записи числа, а i – номер самой левой девятки  из n девяток подряд: =3,141592… f(1) = 5.

Задача состоит  в вычислении функции f(n) для произвольно  заданного n.

Поскольку число  является иррациональным и трансцендентным, то мы не знаем никакой информации о распределении девяток (равно  как и любых других цифр) в десятичной записи числа. Вычисление f(n) связано  с вычислением последующих цифр в разложении, до тех пор, пока мы не обнаружим n девяток подряд, однако у нас нет общего метода вычисления f(n), поэтому для некоторых n вычисления могут продолжаться бесконечно –  мы даже не знаем в принципе (по природе  числа) существует ли решение для  всех n.