Пользователь
0,0
рейтинг
12 августа 2013 в 02:22

Разработка → Brainfuck и фундаментальные ограничения мироздания

Сразу предупреждаю, те, кто учили CS в ВУЗе могут дальше не читать, интересно не будет. Статья больше для программистов-самоучек без формального образования (вроде меня самого), которые не против узнать какой-нибудь интересный факт из теоретической computer science.

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


Для написания брейнфаковской части мультиквайна из статьи Мультиязыковые квайны я воспользовался следующей функцией:

def brainfuck(st): return "".join(["+"*ord(c)+".>" for c in st])


Это самый простой, но при этом самый длинный и неэффективный способ, распечатать заданную строку на Brainfuck (как оказалось, Юсукэ Эндо, в своём уроборосе использовал его же):

>>> brainfuck("Hello world!")
'++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.>+++++++++++++++++++++++++++++++++.>'


Разумеется захотелось сделать более умную функцию, которая позволила бы мне за счёт небольшого увеличения питоновской части квайна сильно уменьшить брейнфаковскую.
Сразу напрашивался вариант где после печати очередного символа не переходим на следующую, пустую ячейку ленты, а вычисляем очередной символ как смещение от предыдущего:

def brainfuck(st):
    cur=0
    result=''
    for l in st:
        diff=ord(l)-cur
        if diff>0: result+='+'*abs(diff)
        if diff<0: result+='-'*abs(diff)        
        result+='.'
        cur=ord(l)
    return result


>>> brainfuck("Hello world!")
'++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+++++++++++++++++++++++++++++.+++++++..+++.-------------------------------------------------------------------------------.+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.--------.+++.------.--------.-------------------------------------------------------------------.'


Стало значительно лучше. Когда я подставил эту новую функцию в квайн, размер брейнфаковской части квайна уменьшился в 1.6 раз. Потом я посмотрел на каноничный пример выводящий 'Hello world' и понял, что, мягко говоря, ещё есть над чем работать:

++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++. >.+++.------.--------.>+.>.


Кроме этого, я увидел, что у меня не получается сходу формализовать устройство этой простенькой программы. Как она работает — вполне понятно (часть программы до знака "]" заполняет на ленте 4 ячейки кодами близкими к кодам букв фразы, а остальная часть программы — finetuning, перемещаемся между символами, тут и там слегка обрабатываем напильником и выводим), а вот как написать программу, которая выдаст её на выходе…

И задался я вопросом — а как написать программу, которая получает строку и выдаёт минимальную программу на brainfuck, которая эту строку выводит. Те, кто учил CS и всё-таки дочитал до этого места сейчас ухмыляются…
Оказалось, что это невозможно. Не потому, что я слабый программист, не из-за того, что такая программа требует каких-то сумасшедших объёмов данных и/или невероятных вычислительных ресурсов. Она просто невозможна, это одно из фундаментальных ограничений нашей несовершенной вселенной. Сейчас приведу доказательство, не строгое, но надеюсь, хотя бы понятное.
Объяснять буду уже на Питоне, т.к. писать нетривиальный код на брейнфаке не умею, да и пониманию доказательства он вряд ли поспособствует, впрочем всё это работает для любого полного по тьюрингу языка программирования.

Итак, докажем от противного. Допустим, путём невероятных усилий нам удалось создать функцию minimal_program, которая получает строку и возвращает код модуля на Питоне, который печатает эту строку, причём этот модуль гарантированно минимально возможного размера.
создадим модуль, в этом модуле будет функция minimal_program, будет вспомогательная функция generate_strings, которая генерирует все возможные строки — сначала строки из одного символа в алфавитном порядке, потом из двух, из трёх и т.д. и будет следующая функция:

def large_string(n):
    for st in generate_strings():
        mp=minimal_program(st)
        if len(mp)>=n:
            return st


Понятно, что эта функция делает — она возвращает строку, для вывода которой нужен модуль размером не менее n символов. А теперь вычисляем размер получившегося модуля, обозначим его MODULE_LEN и дописываем в наш модуль несколько строк:

if "__main__"==__name:
    print large_string(MODULE_LEN*1000)


Итого, что мы имеем? Программу, размером чуть больше MODULE_LEN, которая выводит строку, минимальная программа для вывода которой не может быть меньше MODULE_LEN*1000. Пришли к противоречию, чем доказали неверность исходной посылки — возможности существования функции minimal_program.

Кто-то может поинтересоваться — для доказательства мы построили генератор строк, который перебирает строки до тех пор, пока для генерации очередной строки не понадобится очень большая программа. Но ведь точно так же мы можем перебирать и программы, ведь это, в сущности те же строки! Идём от коротких к длинным, пробуем выполнить. Выдала программа ошибку — ладно, выдала не тот вывод, которого ждали — чёрт с ним. Но ведь в какой-то момент мы дойдём до программы (пусть даже для этого потребуется время большее чем возраст вселенной, мы ведь обсуждаем теоретическую возможность!), которая распечатает нужную нам строку, а так как мы перебираем строки от коротких к длинным, эта программа будет самой короткой! Где ошибка? Ошибка в том, что программы не обязательно завершаются ошибкой или нормальным выходом. Они вообще не обязательно завершаются. А проверка, завершится ли произвольная программа или «зависнет» — ещё одна классическая алгоритмически неразрешимая задача — проблема остановки.

Кстати, это доказательство — совсем не повод не пытаться создавать хорошие алгоритмы архивации и писать генераторы короткого кода на brainfuck (я сам ещё точно попробую)! Просто задачу нужно ставить несколько менее глобальную.

Ссылки для тех, кто хочет углубиться в тему:
Алгоритмически неразрешимые задачи
Колмогоровская сложность
@gromozeka1980
карма
88,5
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (80)

  • 0
    Я плаваю в CS, мягко говоря, но имхо следует различать «в принципе», и «для конкретной строки». Насколько я понимаю, эта задача — задача «занятых бобров» (busy beaver problem), и для очень простых машин Тьюринга она решена в лоб, а для чуть более сложных показано, что решение сильно больше любых разумных ожиданий (что-то типа 1030000).
    • 0
      К бобрам это имеет несколько опосредованное отношение. Там ищут машину Тьюринга данной длинны, генерирующую максимальный вывод. Здесь задача ближе к обычной проблеме остановки.

      На счёт «в принципе» и «для конкретной строки». Из того, что эта проблема не решается в принципе, следует, что существуют конкретные строки, для которых она не решается. Более того, рискну предположить, что самые короткие такие строки будут в пределах десятков символов. Как правильно заметил автор, на практике это будет означать, что для данной строки можно будет найти короткие машины Тьюринга (или BF-программы), которые её генерируют, но про них невозможно доказать, остановятся они, не остановятся, и напечатают ли что-либо ещё.
      • НЛО прилетело и опубликовало эту надпись здесь
        • 0
          Почему нельзя?

          Предположим, что для каждой конкретной строки S можно кратчайшую BF-программу P, которая её генерирует и доказать, что это она. Рассмотрим следующий алгоритм:

          Мы перебираем все возможные доказательства в порядке возрастания длины и для каждого проверяем, не является ли оно доказательством утверждения «программа P является кратчайшей, генерирующей строку S».

          Если для каждой конкретной строки можно найти кратчайшую программу, то этот алгоритм будет всегда останавливаться, и будет решать общую проблему поиска кратчайшей программы для данной строки.
          • НЛО прилетело и опубликовало эту надпись здесь
            • 0
              Из того, что система не полна, не следует что она не формализована или вообще чем-то плоха. Мы же не говорим, что физика «плоха» из-за того, что согласно ей невозможно двигаться быстрее скорости света.

              Понятие «доказать» математиками уже давно и полностью формализовано. Даже несколькими (эквивалентными) способами.

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

                  В таком случае, верно более слабое утверждение, чем то, которое я написал. А именно, для любой наперёд заданной математической теории существует конктретная строка, для которой невозможно найти кратчайшую BF-программу, её выводящую.
                  • НЛО прилетело и опубликовало эту надпись здесь
      • +2
        Здесь задача ближе к обычной проблеме остановки.
        Задача нахождения колмогоровской сложности данной строки
        • 0
          Да, точно, спасибо за поправку.
      • 0
        Если у нас есть решённая задача бобров для данного размера тьюринг-машины, то мы можем просто перебирать все возможные алгоритмы в пределах, установленных бобрами и считать, что алгоритм не завершается, если он работает дольше, чем говорят бобры.

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

        Так что всё сводится к оценке бобров, то есть для машин с размером состояний больше 4, к теоретически «больше, чем можем выдержать».
        • НЛО прилетело и опубликовало эту надпись здесь
          • 0
            Не для любого конечного n, а для очень небольшого количества почти тривиальных случаев. Дальше доказано, что задача растёт непропорционально быстро, более того, показана её нерешаемость для произвольного n.
  • +1
    Надо бы как-то доказать, что этот участок кода:
    if len(mp)>=n:
    return st
    выполнится для произвольно большого n

    хотя это почти очевидно, да…
  • +1
    А чем такая программа не решает исходной задачи:

    введем вспомогательную функцию выполняющую brainfuck код: invoke(s) -> s.
    def brainfuck(st):
    for generated in generate_strings():
    if invoke(generated) == st: return generated

    ?
    • +2
      В статье сказано. Тем, что invoke может подвиснуть
      • 0
        Или если пояснить: generated может рано или поздно оказаться равен for(;;); на брейнфаке.
        • 0
          А если проверять время выполнения и отбраковывать всё, что выполняется слишком долго?
          • +2
            Тогда предложенная программа теоретически не решит поставленной задачи.
            Могу привести вам пример.
            Пусть моя строка $S (из постановки задачи) очень большая, но я знаю ее мд5-хеш $H. И пусть окажется, что кратчайшая программа, выводящая $S, выглядит так:
            for generated in generate_strings():
              if md5(generated) = $H {
                print generated;
                return;
              }    
            

            Так вот эта программа наверняка отсечется любым вменяемым ограничением времени, хотя она является решением. Само сабой, указать такое конечное время, чтобы уж точно хватало, невозможно. Но это всё теория.
            • 0
              Она наедет на коллизию гораздо раньше, чем найдёт правильный ответ, $S же очень большая.
              • 0
                Во-первых, может оказаться, что первое совпадение хеша и окажется искомой строкой $S. Во-вторых, можно возвращать не самую первую, а m-ную строку, у которой md5 совпадает с $H. В таком случае, с незначительным удлиннением программы, можно генерировать очень длинные строки.
                • +1
                  Суть верна, но нельзя так просто «с незначительным удлиннением программы генерировать очень длинные строки». md5-хеш занимает 16 байт, следовательно среди (байтовых) строк из 17 байт будет в среднем по 256 строк с одинаковым md5, и для хранения номера m нужной строки потребуется также 1 байт (также, т.к. 17-16=1). Если бы не это, то можно было бы сделать отличный архиватор, пусть и работающий крайне долго, который сжимал бы любой файл почти до размера хеша от него :)
          • +2
            Вы не сможете придать точный смысл выражению «слишком долго».
          • 0
            К сожалению, принципиально невозможно дать верхнюю границу для времени выполнения программы, после которого она успешно завершится. То есть, какую бы формулу не написали, хоть N^N^N^...^N N раз, настоящее ограничение сверху для времени исполнения программы данной длины будет всё равно больше.
  • –1
    Ошибка в том, что программы не обязательно завершаются ошибкой или нормальным выходом. Они вообще не обязательно завершаются.

    С минимальной программой такая проблема есть, но если несколько ослабить требования, задача становится [теоретически] решаемой: мы можем решить задачу генерации программы на брейнфаке, которая выдает заданную строку тривиально, и для искомой «минимальной» (не обязательно истинно минимальной) ограничить время выполнения скажем 10(100, 1000,...)-кратным временем выполнения тривиального варианта. Опять же это разумно: кому нужна минимальная программа на брейнфаке, выводящая «Hello, World», которая работает, скажем, час. Вообще, мне кажется, тут вдохновение надо искать в архиваторах, как программах по генерации других программ, которые выдаеют разархивированные данные в результате своей работы.
    • +13
      — Голубчики, — сказал Фёдор Симеонович озабоченно, разобравшись в почерках. — Это же проблема Бен Бецалеля. Калиостро же доказал, что она не имеет решения.
      — Мы сами знаем, что она не имеет решения, — сказал Хунта, немедленно ощетиниваясь. — Мы хотим знать, как её решать.
      (с) Стругацкие «Понедельник начинается в субботу»

      Опять же это разумно: кому нужна минимальная программа на брейнфаке, выводящая «Hello, World», которая работает, скажем, час?
      А кому вообще нужна программа на брейнфаке, выводящая «Hello, World»?
      Или даже так — А кому вообще нужна программа на брейнфаке?

      Речь идёт исключительно о теории :)
      А для практиков, можно ещё, к примеру, убрать квадратные скобки из брейнфака, без них на нём невозможно организовать цикл и подвесить программу. Кратчайшую программу на таком брейнфаке вполне можно найти.
  • +5
    Автор, если смотреть с точки зрения CS, то всё чуть проще: вы не можете написать программу, которая по коду будет говорить, выводит ли он «hello world». Не говоря уже о поиске кратчайшего такого кода.
    • 0
      Ну да, именно. У меня вроде как целый абзац об этом.
    • +1
      Но вообще «поиск кратчайшего такого кода» и «генерация кода» — это разные вещи. Мы вполне можем генерировать программы, которые будут выводить то, что нам надо и не гарантированно не виснуть (взять хотя бы оба варианта функции brainfuck), другой вопрос, что никакой алгоритм не сможет для любой строки генерировать кратчайшие программы.
      • 0
        очепятался
        и не гарантированно не виснуть
      • 0
        Да, вынужден согласиться, что мой комментарий не к теме.
  • –1
    А в чём проблема посмотреть остановится ли программа, которая только выводит что-то? На Брайнфаке работа такой программы полностью определяется собственно программой и тем что на ленте, тут зацикливание найти не так уж и сложно. Никаких тебе рандомов, получение текущей даты и прочего внешнего шума.

    Задача остановки не решается в общем виде. В таком частном как программа на Брайнфаке без внешнего ввода — запросто.
    • –2
      Дваждую. Как минимум, можно строго вывести число шагов, за которое программа на Брейнфаке заданной длины должна остановиться, если она останавливается вообще. Хотя число будет страшненькое.
      • 0
        Нет, насколько я понимаю, брейнфак — алгоритмически полный язык, а поэтому либо придется ввести ограничение вроде «если не останавливается за N шагов, то будем считать, что не останавливается вообще», либо ничего не выйдет. Есть теорема об остановке, которая говорит, что единственный способ понять, что выведет данная программа на данном входе (или без входа, не важно) — это интерпретировать ее.
        • 0
          М, да, пардоньте. Я перепутал размер программы с размером ленты.
        • 0
          Мы и так уже ограничение добавляем: никакого внешнего ввода. После этого надо только увидеть, что мы выполняем те же шаги, которые приводят к тем же изменениям на ленте.
          • +2
            Приведу простой пример.
            Числа Ферма, числа вида — image
            Некоторые из чисел Ферма являются так же простыми числами. На данный момент таких найдено 5 — 3, 5, 17, 257, 65537.
            Неизвестно, конечно ли число простых чисел Ферма и если конечно, есть ли ещё что-то кроме этой пятёрки.
            Проверку на то, является ли число простым числом Ферма — написать можно. Бежать подряд по числам — тоже не проблема. Остановиться в случае если нашли частое число — что может быть проще?
            А вот проверить, остановится ли когда-нибудь такая программа (нет внешнего ввода, обратили внимание?)… По крайней мере специалисты в теории чисел ответа на этот вопрос пока не знают…
            • +1
              если нашли шестое число

              кофе мне срочно…
            • –3
              У вас, что называется ус отклеился ряд не сходится. У нас куча ограничений в программе:

              1) размер программы сверху известен (это написание в лоб)
              2) размер на число ячейки сверху есть (это один байт)
              3) внешнего ввода нет

              У вас же неизвестно существует ли вообще решение этой задачи (в нашей случае — 100% существует).
              • +3
                Вы писали:

                А в чём проблема посмотреть остановится ли программа, которая только выводит что-то? На Брайнфаке работа такой программы полностью определяется собственно программой и тем что на ленте, тут зацикливание найти не так уж и сложно. Никаких тебе рандомов, получение текущей даты и прочего внешнего шума.

                Задача остановки не решается в общем виде. В таком частном как программа на Брайнфаке без внешнего ввода — запросто.


                Я привёл Вам пример программы, которая во-первых «только выводит что-то», где нет никаких «рандомов, получение текущей даты и прочего внешнего шума» и главное никаких половых связей никакого внешнего ввода.
                Вы утверждаете, что в программе, удовлетворяющей этим условиям «зацикливание найти не так уж и сложно». Пример показывает, что таки сложно. Во всяком случае, математики до сих пор над этим работают.
                • –2
                  Мы вполне конкретную задачу выводим, а не что угодно. У нас известная строка, известной длины. У вас ваша «строка» потенциально бесконечная.
                  • +3
                    @!%#*&!*)#!@ Ну сколько можно? Есть хороший принцип: если вы свалились в выкопанную вами яму — прекратите копать.

                    Достаточно модифицировать эту программу так, чтобы она напечатала один символ и всё: будет вам программа, которая либо печатает один этот символ, либо ничего не печатает.
                    • –3
                      Что за истерика? Если вам есть что сказать, говорите, а истерить не нужно.

                      Что вы своим «одним символом» собираетесь сказать, я не понял.
    • 0
      Зато размер памяти не ограничен, программа может сколько угодно ячеек заполнить, а соответственно число потенциальных состояний бесконечно. Вот если память тоже ограничить, то программа либо зациклится (повторит своё старое состояние), либо остановиться. И это уже можно отследить, хоть и затратно.
      • –2
        Как не ограничен? В классическом Брейнфаке 30 тысяч ячеек. Можно, конечно, рассмотреть диалекты, но там просто ячеек больше, но они конечны, конечно же. Брейнфак же не теоретический язык, типа ленты Тьюринга.
        • +1
          30000 — это минимум. А вообще обычно память динамически выделяют по мере надобности.
          The brainfuck language uses a simple machine model consisting of the program and instruction pointer, as well as an array of at least 30,000 byte cells.
          • –4
            В классическом Брейфаке — 30000, именно столько было в том самом интерпретаторе от автора языка. Я его считаю эталонным.
          • 0
            Давайте вот с какого конца пойдём.

            Возьмём произвольную фразу и напишем её на Брейнфаке «в лоб», как в статье выше, без циклов. Это будет максимальная длина (обозначим её N) нашей программы, ограничение сверху, длиннее этого писать смысла нет никакого.

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

            Теперь посмотрим циклы.

            Из чего они состоят в Брейнфаке? Из проверки условия («[»), тела и операции возврата на сбалансированную скобку («]»). На сколько позиций мы можем сдвинуться при помощи цикла? Ответ — на бесконечность или какое-то конечное. Бесконечные циклы отличаются тем, что куда-то двигаются, но впереди «на ленте» нет ненулевых элементов. Конечные всегда содержат возврат на итерируемую ячейку, если возврат мы можем осуществить простой операцией, то чтобы сдвинуться вперёд нам придётся использовать операцию сдвига, причём столько, на сколько мы хотим сдвинуться. Даже если мы используем вложенный цикл внутри его где-то должна быть операция сдвига без цикла и возврата. Так как каждый новый цикл сверху может реализовать в максимум умножение, а циклов не может быть более N/2 (одна операция цикла — две инструкции), я этим сейчас пренебрегу, оставлю просто N, оценка сверху для таких циклов — мы можем сдвинуться не более чем NN ячеек.

            А это конечная величина, конечно же.

            Такие рассуждения годятся?
  • +4
    Я знаю, как найти гарантированно минимальный хелловорлд на языке hq9+. А также гарантированно минимальный квайн.
  • +2
    Тут есть одна маленькая, незаметная глазу натяжка.

    Дело в том что Halt problem, как и многие другие неразрешимые проблемы CS имеют место быть для Великой и Ужасной Универсальной Машины Тьюринга (aka UTM).
    Т.е. для вполне сферического коня в вакууме.
    Ибо основное отличие UTM от реальных компьютеров, данных нам в ощущениях — бесконечная память и бесконечное время.
    К счастью в нашем (не)совершенном мире до сих пор не обнаружено ни одного бесконечного компьютера, бесконечного языка или бесконечной памяти.
    :-)

    Поэтому найти кратчайшую программу можно по следующему алгоритму.
    1. Устанавливаем реалистичное ограничение памяти.
    2. Перебираем все возможные программы, как строки. Для каждой программы делаем
    2.1 Создаем хеш, где ключом является образ памяти программы.
    2.2. На каждом шаге программы проверяем — если образ памяти уже существует в хеше, значит программа зациклилась.
    2.3. Если нет — добавляем образ в хеш и переходим к 2.2

    Пункт 2 полностью решает Halt problem.
    И соответственно позволяет перебором найти все что нам надо.

    Разумеется такое решение непрактично, т.к. при любых разумных ограничениях памяти объем хеша растет экспоненциально.

    Но это практическая иллюстрация, что многие математические вещи, построенные на трансфинитной аксиоматике при переходе к реальности могут выглядеть как подсчет ангелов на кончике иглы.

    В жизни все не так, как на самом деле. (с)
    • +3
      Конечно, если доступная память ограничена сверху, то у неё только конечное множество состояний (хотя и весьма большое). Но в результате реализации вашего плана Вы получите не минимальную программу, которая делает что-то, а минимальную программу на данном количестве памяти. И никаких гарантий, что увеличение этого количества не приведёт к сокращению размера программы :).
      • 0
        Именно!
      • +1
        Разумеется, но если я не математик, а инженер, этого достаточно.
        Если у меня на компьютере гигабайт памяти, то я думаю, что для hello world этого хватит.
        :-)
        В большинстве реальных случаев минимальная программа на разумном ограничении памяти будет минимальной и на бесконечной памяти.
        Я сейчас попробовал придумать исключение, пока не получается.
        • 0
          1. В большинстве реальных случаев — конечно :).
          2. Я понимаю, что Вы пример не придумаете. И я его не придумаю, я вообще не спец. Но мы же оба понимаем, что такой пример есть, правда? :)

          Если бы его не было, то мы бы могли решить проблему зависания, просто перебирая все возможные объёмы памяти в сторону увеличения. А нам обоим известно, что эта проблема не решается (хотя по крайней мере один из нас самостоятельно это не докажет даже ради вечного спасения души)

          Но вот тут и зарыт вампир. Очевидно, существуют программы, которые виснут на данном объёме памяти, но успешно завершаются на каком-то большем :).
          • +1
            А вот тут как раз вопрос, где зарыт вампир…
            Большинство реальных программ, если им неизвестен объем памяти (как параметр входа), на некотором объеме памяти могут

            1. вылететь по исключению нехватки памяти (т.е. завершиться)
            2. зависнуть (зациклиться).
            3. нормально заврешиться.

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

            Если же взять «традиционные» программы, которые мы все пишем, то там получается ситуация такая.
            1. Если программа нормально завершилась на меньшем количестве памяти, то она нормально завершится и на большем.
            2. Если длина минимальной программы на памяти N0 равна L0, то на памяти N1>N0 ее длина может быть либо L0, либо L1<L0
            и при N1 стремящемся к бесконечности мы обязательно придем к пределу, причем при конечном N1.
            Этот последний пункт может дать нам идею о нахожнении ненаходимого.

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

            Очевидно, что любая реальная программа сразу рассчитана на ограничения памяти.
            Никто не пишет под бесконечную память, даже программисты, использующие сборщики мусора.
            Адресация больше 64 бит практически не встречается в дикой природе.
            И следовательно все такие программы сразу автоматически удовлетворяют п. 1 и 2.
            Следовательно Halt problem для них не выполняется по определению.

            Есть разумеется и другие отличия, но это главное.

            Я бы переформулировал Halt problem для конечных машин так

            Количество памяти требуемой программе A для определения зацикливания программы B экспоненциально по отношению к ограничениям памяти программы B

            В этом случае все в порядке.

            Есть еще одна идея по обнаружению зацикливания — time restricted machine.
            В которой просто к каждой программе идет таймер, автоматически вырубающей ее по прошествию некоторого времени.
            Множество таких программ включает в себя множеством реально используемых программ — ни один компьютер не живет вечно, все когда-то перегрузится или сломает диск или просто заржавеет.

            Ограничения окружающего мира уже достаточно жесткие, чтобы бесконечность не встречалась нигде, кроме как в математических конструкциях. Соответственно в реальном мире Halt problem не такая уж и страшная вещь.
            • 0
              Всё верно, кроме вывода.

              Ограничения окружающего мира уже достаточно жесткие, чтобы бесконечность не встречалась нигде, кроме как в математических конструкциях.
              А вот и нифига подобного.

              Соответственно в реальном мире Halt problem не такая уж и страшная вещь.
              Погодите. Вы тут описали способ как взять практические ограничения и создать программу, которая теоретически решит поставленную задачу.

              Одна беда: на практике после того, как все звёзды потухнут и чёрные дыры испарятся ваша чудесная программа всё ещё будет что-то такое там считать и перебирать — ну так какой, нафиг, в ней смысл?

              Вы уж определитесь: либо мы рассматриваем теоретические построения и тогда halt problem — таки проблема, либо мы рассматриваем практические ситуация и тогда… halt problem — ещё большая проблема. На практике уже какая-нибудь несчастная обычная экспонента — это проблема, а вы тут рассуждаете об алгоритмах, сложность которых растёт куда более быстрыми темпами (не забываем, что сама память, доступная нам практически, растёт по экспоненте из-за закона Мура).
              • +1
                А вот и нифига подобного.

                Приведите контрпример.

                Бесконечность может встречаться в конструктивных определениях и моделях, но не в окружающем мире.
                Во всяком случае как бы мы тогда ее измерили?
                :-)
                Т.е. построить комбинацию символов, обозначающих повернутую восьмерку мы можем.
                А построить бесконечный компьютер — нет.
                Бесконечность — артефакт языка, а не свойство реальности, чисто Витгенштейновский узелок на языковых конструкциях.

                Одна беда: на практике после того, как все звёзды потухнут и чёрные дыры испарятся ваша чудесная программа всё ещё будет что-то такое там считать и перебирать — ну так какой, нафиг, в ней смысл?


                Ну вот, это вообще-то мой аргумент и моя точка зрения.
                Какой смысл в бесконечных множествах, если их нельзя посчитать.

                На практике, чтобы вывести минимальную программу hello world, или минимальный квайн — не требуется ждать пока черные дыры испарятся.
                Более того, на практике даже не перебирают все состояния — делают лишь разумный сэмплинг и ставят ограничение по времени и памяти.
                Наш генокод между прочим появился в результате такого процесса, и теперь многие считают вероятность его спонтанного появления — пользуясь таким же странным инструментарием.

                Вы уж определитесь


                Повторяю, на практике halt problem не является принципиальным ограничением.
                А является лишь ограничением количественным, которое где-то может играть роль, а где-то не может.

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

                И да, почему у нас сложность растет быстрее экспоненты?
                Если у нас состояние — один байт информации, т.е. 8 бит, то хранить список состояний — максимум 256 бит = 2^8.
                Т.е. имеем верхнюю границу — экспоненциальную.
                Так что средняя сложность будет субэкспонентой.
                А плюс ограничения на программы (например не модифицировать код), плюс эвристики — для конкретных случаев вполне могут снизить сложность еще больше.

                Берем код, ищем циклы, переходы и рекурсии и храним состояния связанные с фрагментами — все, сложность еще понизилась.
                Общей проблемой это не является.
          • НЛО прилетело и опубликовало эту надпись здесь
            • 0
              Минимальная программа для любой строки всегда существует


              Кстати, это неочевидно. Если, например, утверждение «кратчайшая длина программы для Hello World! равна 112» окажется недоказуемым — правда, эта недоказуемость тоже будет недоказуемой :) — то любая программа меньшей длины, для которой не доказано, остановится она или нет, будет кандидатом на «минимальную», но ни одна из этих программ минимальной (в используемой аксиоматике) не будет.
              • НЛО прилетело и опубликовало эту надпись здесь
                • 0
                  Всё равно не понимаю. Если для какой-нибудь машины Тьюринга вопрос остановки недоказуем (или недоказуемо наличие корня какого-то диофантова уравнения) то почему мы не можем добавить к ZFC утверждение, что машина остановится (а у уравнения корни есть)? Ведь противоречия мы получить не можем — иначе у нас было бы докательство от противного?
                  • 0
                    Что вы подразумеваете под недоказуемостью вопроса остановки? Если алгоритм останавливается, то это 100% можно доказать. Если точно нельзя доказать, что алгоритм останавливается, то он 100% не останавливается.
                    • 0
                      Имеется в виду, что из аксиом, скажем, ZFC, нельзя вывести утверждение «данная МТ не остановится» (можно его переформулировать в чисто арифметическом виде — что некоторая последовательность натуральных чисел не будет содержать числа из «множества состояний остановки»). То, что такие МТ существуют — понятно: иначе бы проблема остановки решалась по принципу «переберём все доказательства, пока не найдём доказательство бесконечной работы данной МТ или не дождёмся её остановки». А если утверждение о бесконечной работе не выводится из аксиом — как может его отрицание противоречить им?
                      • НЛО прилетело и опубликовало эту надпись здесь
                        • 0
                          А чем я рискую? Я прекрасно знаю, что какое бы число шагов я не выбрал, программа за это число шагов не остановится — иначе у меня было бы доказательство остановки.
                          • НЛО прилетело и опубликовало эту надпись здесь
                            • 0
                              Да, алгоритма, позволяющего распознать программу с недоказуемым остановом, конечно, тоже нет. Может быть, такая программа прячется среди 40 программ с 5 состояниями, про которые ответ неизвестен, может быть она где-то дальше, но она точно есть.
                    • НЛО прилетело и опубликовало эту надпись здесь
                      • 0
                        Нет, проблема в другом — в выводе «если программа останавливается, то мы можем взять число шагов, за которое она останавливается, и построить доказательство остановки, просто просчитав программу на это число шагов». Если утверждение об остановке дано в качестве дополнительной аксиомы — то эта аксиома позволяет определить некое число шагов Т, и уже из неё следует существование доказательства этой самой остановки (то есть, как бы задача окажется доказуемой в рамках исходной теории). Но когда мы уберём эту аксиому — исчезнет и число Т, а значит, и доказательство?

                        В какой-то статье утверждение об отсутствии решений диофантова уравнения (речь шла о 10-й проблеме Гильберта) имело вид
                        «If ZFC is consistent and proves only true theorems about integers, then the negation of (1) holds.»
                        (здесь (1) — утверждение, что у уравнения есть решение). Так что однозначного «решений нет» они не сказали.
                        • НЛО прилетело и опубликовало эту надпись здесь
                          • 0
                            Мне непонятно, почему не может быть ситуации, когда программа останавливается или не останавливается в зависимости от теории — если в начальной теории доказательства или опровержения останова нет (и аналогичные вопросы про диофантовы уравнения, про проблему Гольдбаха, про последовательность 3n+1...)
                            • НЛО прилетело и опубликовало эту надпись здесь
                              • 0
                                Кажется, понял. Если остановка данной программы недоказуема, но существует доказательство (прямым вычислением), что она не остановится за N шагов, то существует доказательство, что она не остановится за N+1 шаг. Индукция проклятая. И даже отказ от аксиомы выбора не спасёт.
                                Кстати, работают ли утверждения «натуральный ряд линейно упорядочен» и «любое подмножество натурального ряда содержит минимальный элемент» без аксиомы выбора?
                                А про функцию — надо ещё разобраться, что такое «корректно определена». В ней наверняка есть кванторы — и можно ли в такой ситуации гарантировать, что её значения одинаковы в разных моделях? :)
                                Что функция от двух переменных «программа M остановится за T шагов» ведёт себя везде одинаково, я пока не спорю.
                                • НЛО прилетело и опубликовало эту надпись здесь
                                  • 0
                                    Чтобы принять эти аксиомы, надо сначала понять, почему свойство «программа останавливается» не зависит от теории (или от модели?)… но я это уже писал.
                                    • НЛО прилетело и опубликовало эту надпись здесь
                                      • 0
                                        Кстати, не знаете ли вы какой-нибудь книжки, где хорошо проработана математика без аксиомы выбора (аморфные множества, бесконечные множества, конечные по Дедекинду и т.п. экзотика)?
                                • 0
                                  Да, аксиома выбора не нужна для натуральных чисел, они и так упорядочены.
    • +3
      И кстати вдогонку.
      Практиками достаточно давно используются разумные аппроксимации Колмогоровской сложности (которая принципиально невычислима).

      Вот например, для кластеризации литературных текстов — вполне работает.
      Считает правда адски долго…

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.