определение понятия алгоритм
А потом ещё на ВМК бочку катят...
Ну и твое мнение на этот счет? А мы (с ММ) оценим.
Разве ж это вопрос для раздела "Разработка ПО"? Это, скорее, в стади или во флуд... 
тут вводится определение через машину Тьюринга, которое мне нравится
Ну вот на ВМК на 1 курсе такого мнения придерживаются: формальное полное определение алгоритму придумать сложно и в качестве одного из вариантов формализации рассматривают "Машину Тьюринга". Так же рассматривают "Алгоритмы Маркова" и показывают, что они эквивалентны машине Тьюринга.
Про остальное.
Функция - задаёт отображение. А алгоритм, например, задаёт как его вычислить. Из алгоритма следует одна функция, а обратно может быть много или вообще не быть.
А программы - это уже форма записи алгоритма на определённом алгоритмическом языке, у которого есть семантика, которая, собственно, и задаёт интерпретацию этой программы.
Вообще, кстати, все эти заморочки с интерпретациями вроде хорошо проработаны в математической логике и, соответственно, в прологе. Кстати доказывается, что он по выразительным способностям не хуже машины Тьюринга.
Про остальное.
Функция - задаёт отображение. А алгоритм, например, задаёт как его вычислить. Из алгоритма следует одна функция, а обратно может быть много или вообще не быть.
А программы - это уже форма записи алгоритма на определённом алгоритмическом языке, у которого есть семантика, которая, собственно, и задаёт интерпретацию этой программы.
Вообще, кстати, все эти заморочки с интерпретациями вроде хорошо проработаны в математической логике и, соответственно, в прологе. Кстати доказывается, что он по выразительным способностям не хуже машины Тьюринга.
Развитие теории алгоритмов начинается с доказательства К. Гёделем теорем о неполноте формальных систем, включающих арифметику, первая из которых была доказана в 1931 г. Возникшее в связи с этими теоремами предположение о невозможности алгоритмического разрешения многих математических проблем (в частности, проблемы выводимости в исчислении предикатов) вызвало необходимость стандартизации понятия алгоритма. Первые стандартизованные варианты этого понятия были разработаны в 30-х годах XX века в работах А. Тьюринга, А. Чёрча и Э. Поста. Предложенные ими машина Тьюринга, машина Поста и лямбда-исчисление Чёрча оказались эквивалентными друг другу. Основываясь на работах Гёделя, С. Клини ввел понятие рекурсивной функции, также оказавшееся эквивалентным вышеперечисленным.википедия бля
Одним из наиболее удачных стандартизованных вариантов алгоритма является введённое А. А. Марковым понятие нормального алгорифма. Оно было разработано десятью годами позже работ Тьюринга, Поста, Чёрча и Клини в связи с доказательством алгоритмической неразрешимости ряда алгебраических проблем.
> тут вводится определение через машину Тьюринга, которое мне нравится
Во! Первый конструктивный ответ!
Определение через машину Тьюринга неудобно тем, что не позволяет непосредственно рассматривать как алгоритмы такие общеизвестные процедуры как "алгоритм быстрой сортировки", "алгоритм обхода графа в глубину". Т. е. их можно переделать для машины Тьюринга, но необходимо описывать, как хранить массив на ленте и т. п. В равной степени неудобно определение через рекурсивные функции. Для практических нужд (например, для анализа сложности алгоритмов) требуется более "высокоуровневое" определение. Например, чтобы были переменные, память, стек. По этой причине и возник вопрос.
Приведенное определение отлично согласуется с тем, как я до этого понимал алгоритм. Оно отвечает на большинство возникших у нас в дискуссии вопросов.
Приведу пример следствия из этого определения.
Рассмотрим такую строку кода на языке C:
x = a + b + c + d;
где a, b, c, d — некоторые выражения.
Согласно стандарту ANSI C, порядок, в котором вычисляются функции, не оговорен. Можно сначала вычислять a, потом b, потом с, потом d. А можно b, c, a и в конце d. Во всех случаях компилятор будет прав.
Согласно определению:
"4. Последовательность шагов алгоритма детерминированна, т.е. после каждого шага указывается, какой шаг следует выполнять дальше, либо указывается, когда следует работу алгоритма считать законченной."
Таким образом, с формальной точки зрения выражение x = a + b + c + d не дает алгоритма. Для того, чтобы получился алгоритм, необходимо явно указывать порядок вычислений (что выполняется компилятором).
Я нигде не ошибаюсь?
Во! Первый конструктивный ответ!
Определение через машину Тьюринга неудобно тем, что не позволяет непосредственно рассматривать как алгоритмы такие общеизвестные процедуры как "алгоритм быстрой сортировки", "алгоритм обхода графа в глубину". Т. е. их можно переделать для машины Тьюринга, но необходимо описывать, как хранить массив на ленте и т. п. В равной степени неудобно определение через рекурсивные функции. Для практических нужд (например, для анализа сложности алгоритмов) требуется более "высокоуровневое" определение. Например, чтобы были переменные, память, стек. По этой причине и возник вопрос.
Приведенное определение отлично согласуется с тем, как я до этого понимал алгоритм. Оно отвечает на большинство возникших у нас в дискуссии вопросов.
Приведу пример следствия из этого определения.
Рассмотрим такую строку кода на языке C:
x = a + b + c + d;
где a, b, c, d — некоторые выражения.
Согласно стандарту ANSI C, порядок, в котором вычисляются функции, не оговорен. Можно сначала вычислять a, потом b, потом с, потом d. А можно b, c, a и в конце d. Во всех случаях компилятор будет прав.
Согласно определению:
"4. Последовательность шагов алгоритма детерминированна, т.е. после каждого шага указывается, какой шаг следует выполнять дальше, либо указывается, когда следует работу алгоритма считать законченной."
Таким образом, с формальной точки зрения выражение x = a + b + c + d не дает алгоритма. Для того, чтобы получился алгоритм, необходимо явно указывать порядок вычислений (что выполняется компилятором).
Я нигде не ошибаюсь?
> википедия бля
Объясни, пожалуйста, почему quicksort является алгоритмом?
Объясни, пожалуйста, почему quicksort является алгоритмом?
а это уже не математическое понятие, наверное
Определение через машину Тьюринга неудобно тем, что не позволяет непосредственно рассматривать как алгоритмы такие общеизвестные процедуры как "алгоритм быстрой сортировки", "алгоритм обхода графа в глубину".Для этого в математике обычно сводят одно к другому. Берёшь свой "высокоуровневый" язык и доказываешь его эквивалентность машине Тьюринга или другому эквиваленту. Теперь алгоритмы на твоём языке являются алгоритмами.
> А программы - это уже форма записи алгоритма на определённом алгоритмическом языке, у которого есть семантика, которая, собственно, и задаёт интерпретацию этой программы.
Вопрос1: может ли программа задавать алгоритм неоднозначно?
Вопрос2: допустим у нас есть программа. Задает ли она сама по себе алгоритм? Или нужно еще добавить семантику языка, которая описывает, как эти программы вычисляются? Зависит ли это от компилятора?
Что делать если семантика языка неоднозначна или оперирует неалгоритмическими объектами (например, денотационная семантика)?
Вопрос1: может ли программа задавать алгоритм неоднозначно?
Вопрос2: допустим у нас есть программа. Задает ли она сама по себе алгоритм? Или нужно еще добавить семантику языка, которая описывает, как эти программы вычисляются? Зависит ли это от компилятора?
Что делать если семантика языка неоднозначна или оперирует неалгоритмическими объектами (например, денотационная семантика)?
Берёшь свой "высокоуровневый" язык и доказываешь его эквивалентность машине Тьюринга или другому эквиваленту.Там проблема в том, что сложность алгоритма определяется тогда с точностью до полиномиального множителя, а представление данных вообще произвольно, и потому quicksort будет неотличим от пузырька.
Сразу скажу, что для доказательства, что "алгоритм быстрой сортировки" — это именно алгоритм, совершенно необязательно раскручивать до машины Тьюринга. Достаточно до какого-нибудь псевдокода или кода на детерминированном языке (вот, ты показал, что С — недерминированный язык для которого уже отдельно кто-то когда-то доказал, что любая программа на этом языке может быть реализована на машине Тьюринга.
Конкретно про С могу сказать — да, все плохо. Алгоритма мы не получаем.
Конкретно про С могу сказать — да, все плохо. Алгоритма мы не получаем.
допустим у нас есть программа. Задает ли она сама по себе алгоритм?ну например если это SQL или там XSLT какой, то я бы не сказал, что это задаёт алгоритм
> Для этого в математике обычно сводят одно к другому. Берёшь свой "высокоуровневый" язык и
> доказываешь его эквивалентность машине Тьюринга или другому эквиваленту. Теперь алгоритмы на
> твоём языке являются алгоритмами.
Меня выразительность не интересует. Меня интересует прежде всего сложность алгоритмов. Например, я хочу доказать, что сложность быстрой сортировки — O(n log n). Как мне это делать? Если я сведу все к машине Тьюринга, то скорее всего получится какая-то ж@#а и сложность порядка O(n^100).
> доказываешь его эквивалентность машине Тьюринга или другому эквиваленту. Теперь алгоритмы на
> твоём языке являются алгоритмами.
Меня выразительность не интересует. Меня интересует прежде всего сложность алгоритмов. Например, я хочу доказать, что сложность быстрой сортировки — O(n log n). Как мне это делать? Если я сведу все к машине Тьюринга, то скорее всего получится какая-то ж@#а и сложность порядка O(n^100).
Таким образом, с формальной точки зрения выражение x = a + b + c + d не дает алгоритма.А если это назвать действием "сложить 4 числа".
А вообще что ты хочешь этим добиться? Можно сказать, что C - неалгоритмический язык. Примерно так и есть, т.к. из-за такого недетерминизма может измениться результат.
> Конкретно про С могу сказать — да, все плохо. Алгоритма мы не получаем
> ну например если это SQL или там XSLT какой, то я бы не сказал, что это задаёт алгоритм
Картина проясняется! Спасибо и .
Еще хотелось бы понять, дает ли программа на языке X + формальная семантика языка X алгоритм? Могут ли они давать не один алгоритм, а сразу несколько?
> ну например если это SQL или там XSLT какой, то я бы не сказал, что это задаёт алгоритм
Картина проясняется! Спасибо и .
Еще хотелось бы понять, дает ли программа на языке X + формальная семантика языка X алгоритм? Могут ли они давать не один алгоритм, а сразу несколько?
> Объясни, пожалуйста, почему quicksort является алгоритмом?
А ты кандмин уже сдавал? Там точно это называлось алгоритмом?
А ты кандмин уже сдавал? Там точно это называлось алгоритмом?
> ну например если это SQL или там XSLT какой, то я бы не сказал, что это задаёт алгоритм
Можно ли сказать, что программа на декларативном языке (по типу SQL, XSLT, Prolog, Haskell где явно не задается порядок вычислений, не дает алгоритм. Она дает некоторое описание алгоритма, по которому уже компилятор автоматически строит алгоритм?
Или это неверная точка зрения?
Можно ли сказать, что программа на декларативном языке (по типу SQL, XSLT, Prolog, Haskell где явно не задается порядок вычислений, не дает алгоритм. Она дает некоторое описание алгоритма, по которому уже компилятор автоматически строит алгоритм?
Или это неверная точка зрения?
Так ты понятие сложности определи. В частности, для сортировки различают сложность в операциях сравнения и сложность в операциях присваивания (либо перестановки). А можно в процессорных инструкциях мерять или в тактах процессора.
> А ты кандмин уже сдавал? Там точно это называлось алгоритмом?
Сдавал. Точно называлось.
Сдавал. Точно называлось.
Меня выразительность не интересует. Меня интересует прежде всего сложность алгоритмов.А, ну так с этого надо было начинать.
Я думаю, что компилятор преобразует код. А алгоритм - это абстракция, могущая в зависимости от ситуации иметь большую или меньшую полезность для анализа этих процессов.
Да, программа на алгоритмическом языке задаёт алгоритм, я думаю. Программы на Прологе, на "машине Тьюринга", на "алгоритмах Маркова" задают алгоритм.
Когда говорят про вычислительную сложноть, то работают в рамках определённой модели. Т.к. понятие сложности сильно привязано к модели вычислений.
Когда говорят про вычислительную сложноть, то работают в рамках определённой модели. Т.к. понятие сложности сильно привязано к модели вычислений.
> Да, программа на алгоритмическом языке задаёт алгоритм, я думаю. Программы на Прологе, на "машине Тьюринга", на "алгоритмах Маркова" задают алгоритм.
Что такое алгоритмический язык? Являются ли алгоритмическими языки C, SQL, Prolog?
> Когда говорят про вычислительную сложноть, то работают в рамках определённой модели.
> Т.к. понятие сложности сильно привязано к модели вычислений.
А вот когда говорят фразы типа "quicksort имеет сложность O(n log n)" какую модель имеют ввиду? Есть какая-то общепринятая модель, которую все используют? Или же эта модель включается в формулировку утверждения о сложности?
Может быть, эта модель включается в описание самого алгоритма?
Еще такой вопрос. Допустим, в книжке написан некоторый алгоритм и указано, что он имеет сложность O(n^log n). Вася Пупкин взял некоторый распространенный язык программирования и реализовал в нем этот алгоритм. Непосредственные замеры показывают, что время работы программы Васи Пупкина зависит от длины входных данных как O(n^2). Что это значит?
1) Вася Пупкин криво реализовал алгоритм?
2) Если Вася Пупкин реализовал алгоритм в строгом соответствии с книжкой, то это значит что виноват компилятор?
Еще бывают некоторые языки, где сложность вычисления тех или иных конструкций не указывается в стандарте. Вот возьмем например Haskell. Рассмотрим вычисление в Haskell суммы первых n чисел:
Налицо какая-то нетривиальная зависимость объема используемой памяти и времени вычислений (даже нелинейная).
Можно ли считать, что функция \n -> foldl (+) 0 [1..n] реализует тривиальный алгоритм вычисления суммы первых n чисел, если у них разная временная и пространственная сложность?
Сказать, что компилятор кривой здесь нельзя — язык не определяет, сколько времени должны выполняться операции.
Что такое алгоритмический язык? Являются ли алгоритмическими языки C, SQL, Prolog?
> Когда говорят про вычислительную сложноть, то работают в рамках определённой модели.
> Т.к. понятие сложности сильно привязано к модели вычислений.
А вот когда говорят фразы типа "quicksort имеет сложность O(n log n)" какую модель имеют ввиду? Есть какая-то общепринятая модель, которую все используют? Или же эта модель включается в формулировку утверждения о сложности?
Может быть, эта модель включается в описание самого алгоритма?
Еще такой вопрос. Допустим, в книжке написан некоторый алгоритм и указано, что он имеет сложность O(n^log n). Вася Пупкин взял некоторый распространенный язык программирования и реализовал в нем этот алгоритм. Непосредственные замеры показывают, что время работы программы Васи Пупкина зависит от длины входных данных как O(n^2). Что это значит?
1) Вася Пупкин криво реализовал алгоритм?
2) Если Вася Пупкин реализовал алгоритм в строгом соответствии с книжкой, то это значит что виноват компилятор?
Еще бывают некоторые языки, где сложность вычисления тех или иных конструкций не указывается в стандарте. Вот возьмем например Haskell. Рассмотрим вычисление в Haskell суммы первых n чисел:
Prelude> foldl (+) 0 [1..100000]
5000050000
(0.10 secs, 13589596 bytes)
Prelude> foldl (+) 0 [1..200000]
20000100000
(0.35 secs, 31319612 bytes)
Prelude> foldl (+) 0 [1..300000]
45000150000
(0.77 secs, 53215712 bytes)
Prelude> foldl (+) 0 [1..500000]
125000250000
(2.01 secs, 80880052 bytes)
Налицо какая-то нетривиальная зависимость объема используемой памяти и времени вычислений (даже нелинейная).
Можно ли считать, что функция \n -> foldl (+) 0 [1..n] реализует тривиальный алгоритм вычисления суммы первых n чисел, если у них разная временная и пространственная сложность?
Сказать, что компилятор кривой здесь нельзя — язык не определяет, сколько времени должны выполняться операции.
Меня интересует прежде всего сложность алгоритмовсоглашусь с , такого понятия нет.
если понятие: сложность алгоритма при выполнении вот таким исполнителем, соответственно плохо понятно как ты собрался прикручивать формальное определение алгоритма к оценке кол-ва инструкций на конкретном исполнителе
Что такое алгоритмический язык? Являются ли алгоритмическими языки C, SQL, Prolog?Я подразумевал эквивалентность машине Тьюринга. Про C и Prolog тут уже сказано. SQL - трудно сказать. Хотя в нём были добавлены и возможности писать обычные процедуры, но вообще это язык запросов ведь и описывает он немного другое. Если переписать его стандартную семантику, то можно уже смотреть будет ли он эквивалентен или нет.
А вот когда говорят фразы типа "quicksort имеет сложность O(n log n)" какую модель имеют ввиду? Есть какая-то общепринятая модель, которую все используют? Или же эта модель включается в формулировку утверждения о сложности?В случае с сортировками - уже говорили. Там измеряют сложность по количеству сравнений и количеству перемещений.
Может быть, эта модель включается в описание самого алгоритма?Не должна. Скорее тогда включается в описание класса задач "сортировки" в данном случае.
Еще такой вопрос. Допустим, в книжке написан некоторый алгоритм и указано, что он имеет сложность O(n^log n). Вася Пупкин взял некоторый распространенный язык программирования и реализовал в нем этот алгоритм. Непосредственные замеры показывают, что время работы программы Васи Пупкина зависит от длины входных данных как O(n^2). Что это значит?Семантика распространённого языка и метаязыка в книжке могут быть похожими, но в то же время отличаться. Так же компилятор может влиять на скорость вычислений, есть же оптимизирующие компиляторы. Кроме того архитектура может влиять - операции с числами и тому подобное.
1) Вася Пупкин криво реализовал алгоритм?
2) Если Вася Пупкин реализовал алгоритм в строгом соответствии с книжкой, то это значит что виноват компилятор?
Можно ли считать, что функция \n -> foldl (+) 0 [1..n] реализует тривиальный алгоритм вычисления суммы первых n чисел, если у них разная временная и пространственная сложность?У них - это у кого? Алгоритм справляется с задачей. Как и quicksort, bubble sort - это алгоритмы сортировки. Они решают одну и ту же задачу.
Проблема ещё в том, что слово "алгоритм" в разных контекстах имеет разные значения. Когда мы говорим что алгоритм делает, то нам не важно какой он - мы говорим алгоритм сортировки. А если мы измеряем скорость, то мы уже выделяем разные реализации. Т.е. я хочу сказать, что вопрос "являются ли эти сложения одинаковыми алгоритмами, хотя они работают за разное время", является некорректным. Надо уточнять в рамках чего мы сравниваем. Да, они являются оба алгоритмами вычисления первых N чисел. Но они написаны даже на разных языках, поэтому в плане скорости их измерять нельзя (сами алгоритмы). Алгоритм - это не только программа, но и язык, на котором она написана, иначе как его интерпретировать. А Haskell не получится рассматривать для сравнения скорости, т.к. семантика её не определят, и чтобы сравнивать его с C, придётся сравнивать уже компилятор. Т.к. архитектура у нас не для Haskell, а для ассемблера и скорость уже будет меряться на его алгоритмах (программах которые выдаст компилятор.
Вот, какой-то поток сознания вылез.
если понятие: сложность алгоритма при выполнении вот таким исполнителем, соответственно плохо понятно как ты собрался прикручивать формальное определение алгоритма к оценке кол-ва инструкций на конкретном исполнителеВот это как раз пример того, что слово "алгоритм" в разных случаях имеет разный смысл. То есть если мы говорим про сложность, то в данном случае мы будем подразумевать только программы для данного исполнителя, и общее понятие алгоритма применять уже не можем.
А вот когда говорят фразы типа "quicksort имеет сложность O(n log n)" какую модель имеют ввиду? Есть какая-то общепринятая модель, которую все используют? Или же эта модель включается в формулировку утверждения о сложности?Про quicksort - считают число полуформально определённых шагов программы.
В некоторых других случаях, например в курсе численных методов у нас, считались отдельно операции типа сложения и типа умножения.
В обеих этих ситуациях для полностью формального описания следовало бы определить формальную модель вычислений с памятью и инструкциями абстрактной машины, и считать эти инструкции.
Непосредственные замеры показывают, что время работы программы Васи Пупкина зависит от длины входных данных как O(n^2).Если говорить формально, то никакое конечное число замеров не может этого показать.
имхо, после ознакомления с принципами работы квантовых компьютеров, общепринятое определение "сложности" алгоритма нужно пересматривать и расширять
для решения задачи топикстартера, нужна привязка к конкретному исполнителю. это факт
для решения задачи топикстартера, нужна привязка к конкретному исполнителю. это факт
Сложность быстрой сортировки: O(1) Всегда требуется только один вызов функции qsort
Есть интуитивное понятие алгоритма как идеи, основанное на опыте дрессировки мартышек и программирования компьютеров. Его хватает для многих целей. Есть тезис Черча, который позволяет считать использование этого понимания строгим.
Если тебя интересует сложность, то стоит определить, какие операции вообще есть, и какие из них мы считаем. То есть на самом деле определить некую абстрактную машину. Алгоритм тогда — программа на этой машине.
Если ты согласен, что некоторые детали чисто технические, то в описании машины эти детали можно опустить или вообще всю машину подразумевать.
Есть интуитивное понятие алгоритма как идеи, основанное на опыте дрессировки мартышек и программирования компьютеров. Его хватает для многих целей. Есть тезис Черча, который позволяет считать использование этого понимания строгим.
Если тебя интересует сложность, то стоит определить, какие операции вообще есть, и какие из них мы считаем. То есть на самом деле определить некую абстрактную машину. Алгоритм тогда — программа на этой машине.
Если ты согласен, что некоторые детали чисто технические, то в описании машины эти детали можно опустить или вообще всю машину подразумевать.
> Разве ж это вопрос для раздела "Разработка ПО"? Это, скорее, в стади или во флуд...
+1
+1
> общепринятое определение "сложности" алгоритма нужно пересматривать и расширять
"Общепринятое" определение сложности относится к современным процессорным архитектурам и определением является постольку-поскольку. Нестрогим, то есть.
А научные определения есть вот тут: http://en.wikipedia.org/wiki/List_of_complexity_classes, можно ффтыкать до полного просветления =)
"Общепринятое" определение сложности относится к современным процессорным архитектурам и определением является постольку-поскольку. Нестрогим, то есть.
А научные определения есть вот тут: http://en.wikipedia.org/wiki/List_of_complexity_classes, можно ффтыкать до полного просветления =)
>> Что такое алгоритмический язык? Являются ли алгоритмическими языки C, SQL, Prolog?
> Я подразумевал эквивалентность машине Тьюринга. Про C и Prolog тут уже сказано. SQL - трудно
В каком смысле эквивалентность? Тут в треде указывались соображения, что одна программа на языке C может задавать сразу много алгоритмов. Если каждая программа задавала бы ровно один алгоритм, то можно было бы сказать, что язык алгоритмический, если он позволяет записать любой алгоритм для машины Тьюринга. А с этой неоднозначностью — непонятно.
> В случае с сортировками - уже говорили. Там измеряют сложность по количеству сравнений и
> количеству перемещений.
Такие формулировки неявно делают допущения относительно модели вычисления. В некоторых моделях вычисления, например рекурсивных функциях, нет никаких перемещений — там вообще нет памяти. Я хочу выделить эти допущения явно. Например, в качестве вычислительной машины подразумевается стандартная модель с произвольным доступом к памяти за константное время.
> Семантика распространённого языка и метаязыка в книжке могут быть похожими, но в то же время
> отличаться. Так же компилятор может влиять на скорость вычислений, есть же оптимизирующие
> компиляторы. Кроме того архитектура может влиять - операции с числами и тому подобное.
Насколько я понимаю, влияние компилятора, архитектуры процессора должно быть не более, чем в константное число раз. Если компилятор превращает O(n^log n) в O(n^2) — это imho уже бага компилятора.
> У них - это у кого? Алгоритм справляется с задачей. Как и quicksort, bubble sort - это алгоритмы сортировки. Они решают одну и ту же задачу.
Алгоритмы quicksort и bubble sort вычисляют одну и ту же функцию (где функция понимается как подмножество декартового произведения). Но равенство функций не означает, что алгоритмы одинаковые.
> Алгоритм - это не только программа, но и язык, на котором она написана, иначе как его
> интерпретировать.
О! Это ключевая фраза, она все объясняет.
> Я подразумевал эквивалентность машине Тьюринга. Про C и Prolog тут уже сказано. SQL - трудно
В каком смысле эквивалентность? Тут в треде указывались соображения, что одна программа на языке C может задавать сразу много алгоритмов. Если каждая программа задавала бы ровно один алгоритм, то можно было бы сказать, что язык алгоритмический, если он позволяет записать любой алгоритм для машины Тьюринга. А с этой неоднозначностью — непонятно.
> В случае с сортировками - уже говорили. Там измеряют сложность по количеству сравнений и
> количеству перемещений.
Такие формулировки неявно делают допущения относительно модели вычисления. В некоторых моделях вычисления, например рекурсивных функциях, нет никаких перемещений — там вообще нет памяти. Я хочу выделить эти допущения явно. Например, в качестве вычислительной машины подразумевается стандартная модель с произвольным доступом к памяти за константное время.
> Семантика распространённого языка и метаязыка в книжке могут быть похожими, но в то же время
> отличаться. Так же компилятор может влиять на скорость вычислений, есть же оптимизирующие
> компиляторы. Кроме того архитектура может влиять - операции с числами и тому подобное.
Насколько я понимаю, влияние компилятора, архитектуры процессора должно быть не более, чем в константное число раз. Если компилятор превращает O(n^log n) в O(n^2) — это imho уже бага компилятора.
> У них - это у кого? Алгоритм справляется с задачей. Как и quicksort, bubble sort - это алгоритмы сортировки. Они решают одну и ту же задачу.
Алгоритмы quicksort и bubble sort вычисляют одну и ту же функцию (где функция понимается как подмножество декартового произведения). Но равенство функций не означает, что алгоритмы одинаковые.
> Алгоритм - это не только программа, но и язык, на котором она написана, иначе как его
> интерпретировать.
О! Это ключевая фраза, она все объясняет.
> В обеих этих ситуациях для полностью формального описания следовало бы определить формальную
> модель вычислений с памятью и инструкциями абстрактной машины, и считать эти инструкции.
А что делать, если модель вычислений не имеет памяти? Например, функциональные языки определяются через lambda-исчисление. Там нет операции чтения и записи в память. Зато есть операции создания замыкания и применения.
Допустим мы реализовали некоторый метод вычисления на императивном и функциональном языке. В первом случае — у нас A операций чтения, B операций записи. Во втором — C операций создания замыканий, D операций применения. Допустим, нам повезло и A+B=C+D. Можно ли сказать, что это — разные реализации одного и того же алгоритма? Если да, то можно ли считать, что у них одинаковая сложность? Что делать, если вдруг оказалось, что A+B асимптотически больше, чем C+D?
> Если говорить формально, то никакое конечное число замеров не может этого показать.
Ок, можно делать так. Семантика Haskell определяется через lambda-исчисление. Берем программу на Haskell, убираем весь syntactic sugar. Получается большое длинное lambda-выражение. Теперь берем операционную семантику lambda-исчисления и считаем количество редукций для приведения к нормальной форме (порядок редукций смотрим в статье про семантику Haskell). Допустим получается нечто, отличное от O(n). На этот раз это будет строго формальное утверждение, в отличии от замеров времени работы программы. Что в таком случае делать — считать такую реализацию алгоритма правильной или нет?
> модель вычислений с памятью и инструкциями абстрактной машины, и считать эти инструкции.
А что делать, если модель вычислений не имеет памяти? Например, функциональные языки определяются через lambda-исчисление. Там нет операции чтения и записи в память. Зато есть операции создания замыкания и применения.
Допустим мы реализовали некоторый метод вычисления на императивном и функциональном языке. В первом случае — у нас A операций чтения, B операций записи. Во втором — C операций создания замыканий, D операций применения. Допустим, нам повезло и A+B=C+D. Можно ли сказать, что это — разные реализации одного и того же алгоритма? Если да, то можно ли считать, что у них одинаковая сложность? Что делать, если вдруг оказалось, что A+B асимптотически больше, чем C+D?
> Если говорить формально, то никакое конечное число замеров не может этого показать.
Ок, можно делать так. Семантика Haskell определяется через lambda-исчисление. Берем программу на Haskell, убираем весь syntactic sugar. Получается большое длинное lambda-выражение. Теперь берем операционную семантику lambda-исчисления и считаем количество редукций для приведения к нормальной форме (порядок редукций смотрим в статье про семантику Haskell). Допустим получается нечто, отличное от O(n). На этот раз это будет строго формальное утверждение, в отличии от замеров времени работы программы. Что в таком случае делать — считать такую реализацию алгоритма правильной или нет?
> Есть интуитивное понятие алгоритма как идеи, основанное на опыте дрессировки мартышек и
Меня интересует не интуитивное понятие алгоритма, а строгое математическое определение (см. внимательно первый пост).
Интуитивное понятие алгоритма непригодно для исследования алгоритмов. Возьми в качестве примера интуитивное понятие множества. Его использование быстро приводит к неприятностям, например, парадоксу Рассела. С алгоритмами — аналогичная ситуация.
Меня интересует не интуитивное понятие алгоритма, а строгое математическое определение (см. внимательно первый пост).
Интуитивное понятие алгоритма непригодно для исследования алгоритмов. Возьми в качестве примера интуитивное понятие множества. Его использование быстро приводит к неприятностям, например, парадоксу Рассела. С алгоритмами — аналогичная ситуация.
А что делать, если модель вычислений не имеет памяти? Например, функциональные языки определяются через lambda-исчисление. Там нет операции чтения и записи в память. Зато есть операции создания замыкания и применения.При таких разных моделях вычислений сложность просто так не сравнить. Но классы сложности, о которых говорилось выше, сохранятся.
Допустим мы реализовали некоторый метод вычисления на императивном и функциональном языке. В первом случае — у нас A операций чтения, B операций записи. Во втором — C операций создания замыканий, D операций применения. Допустим, нам повезло и A+B=C+D. Можно ли сказать, что это — разные реализации одного и того же алгоритма? Если да, то можно ли считать, что у них одинаковая сложность? Что делать, если вдруг оказалось, что A+B асимптотически больше, чем C+D?
Берем программу на Haskell, убираем весь syntactic sugar. Получается большое длинное lambda-выражение. Теперь берем операционную семантику lambda-исчисления и считаем количество редукций для приведения к нормальной форме (порядок редукций смотрим в статье про семантику Haskell).Ты quicksort на таком не реализуешь, так как не будет массивов и перестановок. А если реализуешь их, то за неконстантное число редукций.
> При таких разных моделях вычислений сложность просто так не сравнить. Но классы сложности,
> о которых говорилось выше, сохранятся.
Стало понятно. Спасибо!
> Ты quicksort на таком не реализуешь, так как не будет массивов и перестановок. А если реализуешь
> их, то за неконстантное число редукций.
Но ведь как-то же оно работает в Haskell?
Кстати, бывает и такое http://paste.lisp.org/display/33688
> о которых говорилось выше, сохранятся.
Стало понятно. Спасибо!
> Ты quicksort на таком не реализуешь, так как не будет массивов и перестановок. А если реализуешь
> их, то за неконстантное число редукций.
Но ведь как-то же оно работает в Haskell?
Кстати, бывает и такое http://paste.lisp.org/display/33688
> тут вводится определение через машину Тьюринга, которое мне нравитсяВо-первых на МаТИСе, на сайт которого дана ссылка, понятие алгоритма принято считать аксиоматическим, а товарищ Носов, в тексте которого нашлось объяснение понятия алгоритма при помощи аналогии с машиной Тьюринга, уже не маленький и людей в таком возрасте (и состоянии) на кафедре не трогают, поскольку кончтруктивного спора там все равно не получится.
Так что не советую серьезно воспринимать то, что там написано.
Щас попробую выебнуться. 
ИМХО, алгоритм - конечный автомат, соответствующий некоей вычислимой функции f, обладающий следующими свойствами:
1) существует отображение I из области определения f в область состояний алгоритма;
2) существует отображение R из области конечных состояний алгоритма в область значений f;
3) f = R * W * I, где W - функция, состоянию алгоритма S сопоставляющая конечное состояние, в которое он приходит из S, а * - знак композиции.
Только учтите, что я механик и никогда в жизни (после шестого класса) с книжным определением алгоритма не сталкивался.
Тогда вот:
Кроме того, W может представляться как композиция W1 * W2 * W3 * ..., тогда это (грубо) подпрограммы (нужно формально определить, чтоб ввести, скажем, понятие CFG).
Один алгоритм может записываться разными программами (T не является инъекцией).
Компьютер - физич. система (память - подсистема ее).
В фазовом пространстве сей системы выделяются подобласти, сопоставляемые состояниям некоего алгоритма.
При этом уравнения движения составлены так, чтоб система двигалась между этими областями в соответствии с алгоритмом.
Вот.
ЗЫ. Вычислимая функция - функция, для которой можно построить алгоритм в виде машины Тьюринга (а также нормального алгорифма Маркова и вообще чего угодно).
ИМХО, алгоритм - конечный автомат, соответствующий некоей вычислимой функции f, обладающий следующими свойствами:
1) существует отображение I из области определения f в область состояний алгоритма;
2) существует отображение R из области конечных состояний алгоритма в область значений f;
3) f = R * W * I, где W - функция, состоянию алгоритма S сопоставляющая конечное состояние, в которое он приходит из S, а * - знак композиции.
Только учтите, что я механик и никогда в жизни (после шестого класса) с книжным определением алгоритма не сталкивался.
Тогда вот:
Кроме того, представляет интерес то, как связаны между собой следующие понятия:См. выше.
1) алгоритм;
2) функция;
Кроме того, W может представляться как композиция W1 * W2 * W3 * ..., тогда это (грубо) подпрограммы (нужно формально определить, чтоб ввести, скажем, понятие CFG).
3) программа как последовательность букв;Слово, для которого существует функция T (транслятор сопоставляющая алгоритм.
Один алгоритм может записываться разными программами (T не является инъекцией).
4) программа как процесс в памяти компьютера.Плз., поточнее, как процесс или в памяти компьютера? "Тот процесс еще на памяти моей..."
Компьютер - физич. система (память - подсистема ее).
В фазовом пространстве сей системы выделяются подобласти, сопоставляемые состояниям некоего алгоритма.
При этом уравнения движения составлены так, чтоб система двигалась между этими областями в соответствии с алгоритмом.
Вот.
ЗЫ. Вычислимая функция - функция, для которой можно построить алгоритм в виде машины Тьюринга (а также нормального алгорифма Маркова и вообще чего угодно).
алгоритм - конечный автоматЭто точно неверно. Попробуй построить конечный автомат для сортировки N чисел в массиве.
Да знаю я. Меня и самого поразила эта фраза, когда я не давно отдыхал вечером у камина с книжкою. Но поразмыслив, я решил что это по-далиански и в духе философии неопрагматизма, и что машина Тьюринга - это конечный автомат с маркетингом (в виде очень длинной ленты). Конечный автомат с фичами.
Тут весь вопрос - включать N чисел внутрь автомата или не включать?
Можно, совсем не употребляя слова "автомат", сослаться на Тьюринга или (лучше) на Маркова. Или на еще кого-нибудь из толпы народа, придумывавшего такие машины, какие только потребуются.
Тут весь вопрос - включать N чисел внутрь автомата или не включать?
Можно, совсем не употребляя слова "автомат", сослаться на Тьюринга или (лучше) на Маркова. Или на еще кого-нибудь из толпы народа, придумывавшего такие машины, какие только потребуются.
а это так и есть, только у него размер сурперэкспоненциальный.
а все эти языки и абстрактные модели вычислительных машин просто способы понять его с помощью вашего несовершенного человеческого разума.
а все эти языки и абстрактные модели вычислительных машин просто способы понять его с помощью вашего несовершенного человеческого разума.
Не раскрыта тема остановки. Ну, вот там где ты говоришь про "область конечных состояний автомата", ты неявно очень страшные и могучие вещи подтягиваешь.
Не раскрыта тема вычислительной сложности алгоритма. Если бы ты сходил по моей ссылочге и потыкал в разные места, то увидел бы, что большинство классов подразумевает сильно подпатченную машину Тьюринга и специфические критерии оценки ответа.
Кстати, а что будем делать с невычислимыми функциями?
Не раскрыта тема вычислительной сложности алгоритма. Если бы ты сходил по моей ссылочге и потыкал в разные места, то увидел бы, что большинство классов подразумевает сильно подпатченную машину Тьюринга и специфические критерии оценки ответа.
Кстати, а что будем делать с невычислимыми функциями?
Знания мои имхо поверхностны, но выложу все что мне известно:
Основная мысль - алгоритм это такая штука, которая задает функцию, но все же связана с некоторой последовательностью выполнения действий.
(например
(Колмогоров): Алгоритм – это всякая система вычис-лений, выполняемых по строго определенным правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.
(Марков): Алгоритм – это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату.
Как определяются рекурсивные функции, машина тьюринга и алгоритмы маркова писать не буду, т.к. имхо это проще отдельно найти в инете.
)
Формальные определения алгоритма:
1. Рекурсивные функции.
2. Машина Тьюринга.
3. Нормальные алгоритмы Маркова.
4. Машина Поста.
Для всех этих моделей доказано, что множества функций которые они задают равны.
Соответствие между алгоритмом и функцией в одну сторону определяется понятием алгоритмическая разрешимость.
В другую сторону почти все очевидно, кроме случаев, когда алгоритм никогда не завершает работу для некоторых входных параметров.
Программа как последовательность букв соотносится с понятием алгоритма в зависимости от математической модели языка программирования, на котором она написана. На сколько я понимаю, наиболее близки к каким-либо формальным моделям функциональные языки.
Основная мысль - алгоритм это такая штука, которая задает функцию, но все же связана с некоторой последовательностью выполнения действий.
(например
(Колмогоров): Алгоритм – это всякая система вычис-лений, выполняемых по строго определенным правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.
(Марков): Алгоритм – это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату.
Как определяются рекурсивные функции, машина тьюринга и алгоритмы маркова писать не буду, т.к. имхо это проще отдельно найти в инете.
)
Формальные определения алгоритма:
1. Рекурсивные функции.
2. Машина Тьюринга.
3. Нормальные алгоритмы Маркова.
4. Машина Поста.
Для всех этих моделей доказано, что множества функций которые они задают равны.
Соответствие между алгоритмом и функцией в одну сторону определяется понятием алгоритмическая разрешимость.
В другую сторону почти все очевидно, кроме случаев, когда алгоритм никогда не завершает работу для некоторых входных параметров.
Программа как последовательность букв соотносится с понятием алгоритма в зависимости от математической модели языка программирования, на котором она написана. На сколько я понимаю, наиболее близки к каким-либо формальным моделям функциональные языки.
сурперэкспоненциальныйНеправда. От того, что N будет больше чем память компьютера, алгоритм не изменится.
ИМХО, алгоритм - конечный автомат, соответствующий некоей вычислимой функции f, обладающий следующими свойствами:
1) существует отображение I из области определения f в область состояний алгоритма;
2) существует отображение R из области конечных состояний алгоритма в область значений f;
3) f = R * W * I, где W - функция, состоянию алгоритма S сопоставляющая конечное состояние, в которое он приходит из S, а * - знак композиции.
Только учтите, что я механик и никогда в жизни (после шестого класса) с книжным определением алгоритма не сталкивался.
Кстати на счет конечного автомата и т.п., машина тьюринга похожа по своему определению на конечный автомат, но всеже является его расширением.
Множество автоматных функций является подмножеством множества вычислимых функций.
> (Колмогоров): Алгоритм – это всякая система вычис-лений, выполняемых по строго определенным правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.
> (Марков): Алгоритм – это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату.
Вопрос заключается в том, что значит строго определенные правила?
Допустим, у нас есть некоторая процедура вычислений, некоторые пункты в которой описаны неоднозначно, размыто.
Например, один из шагов может формулироваться так: "Шаг 17. В переменную X записывается какое-нибудь решение уравнения f(x) = 0". При этом не говорится, как это уравнение решать, и какой именно корень следует выбирать, если их много.
Другой вариант. "Шаг 18. Выберем какое-нибудь натуральное n. Проведем шаги 19-45. Если шаге 45 получилась лажа, вернуться в шаг 18, попробовать какое-нибудь другое натуральное n" (опять не указывается как его выбирать, и сколько раз нужно повторять все это).
Может ли описанный таким образом метод вычислений считаться алгоритмом? Насколько строго требуется описывать процесс вычислений? Насколько допустимы в нем фразы типа "возьмем какое-нибудь n".
Если у нас есть метод вычислений, но не доказано, что он завершается за конечное время, то можно ли считать его алгоритмом?
> (Марков): Алгоритм – это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату.
Вопрос заключается в том, что значит строго определенные правила?
Допустим, у нас есть некоторая процедура вычислений, некоторые пункты в которой описаны неоднозначно, размыто.
Например, один из шагов может формулироваться так: "Шаг 17. В переменную X записывается какое-нибудь решение уравнения f(x) = 0". При этом не говорится, как это уравнение решать, и какой именно корень следует выбирать, если их много.
Другой вариант. "Шаг 18. Выберем какое-нибудь натуральное n. Проведем шаги 19-45. Если шаге 45 получилась лажа, вернуться в шаг 18, попробовать какое-нибудь другое натуральное n" (опять не указывается как его выбирать, и сколько раз нужно повторять все это).
Может ли описанный таким образом метод вычислений считаться алгоритмом? Насколько строго требуется описывать процесс вычислений? Насколько допустимы в нем фразы типа "возьмем какое-нибудь n".
Если у нас есть метод вычислений, но не доказано, что он завершается за конечное время, то можно ли считать его алгоритмом?
> Щас попробую выебнуться.
Тот же самый вопрос: если на некотором шаге указывается несколько возможных путей выполнения, но не указывается какой именно следует из них выбирать, то является ли такой метод вычисления алгоритмом?
Тот же самый вопрос: если на некотором шаге указывается несколько возможных путей выполнения, но не указывается какой именно следует из них выбирать, то является ли такой метод вычисления алгоритмом?
Читать все заебало, поэтому если в чем-то повторюсь - то извините.
Понятие алгоритма сложно формализовать.
Но есть определенные подходы - машина Тьюринга, лямда исчисление Черча, алгоритмы Маркова.
Вроде где-то доказывается, что эти подходы имеют равнозначные выразительные возможности.
И для тех или иных теоретических рассуждений нужно выбирать то, что наиболее удобно в использовании, либо придумать свой механизм элементарных вычислений. // если удастся
Чтобы задать ЯП, нужно задать его синтаксис и семантику его конструкций (кажется это называется операционная семантика ЯП).
Синтаксис задается грамматикой (контекстно свободной или контекстно зависимой - это как уж автору будет угодно)
Операционная семантика ЯП - это формальный механизм доказательства корректности программы на данном ЯП.
Т.е. должна давать ответ на вопрос - является ли данная программа корректной программой на данном ЯП.
По этой теме лучше почитать теорию. Ключевая фраза - формальная спецификация программ (или ЯП).
Для практических современных ЯП формального описания семантики вроде как не существует. Видимо по причине того, что они проектировались без учета данного понятия, так сказать по наитию авторов этих ЯП. Поэтому все материалы по формальной спецификации в основном имеют примеры с игрушечными ЯП.
Как известно, существуют компилируемые и интерпретируемые ЯП.
Формальной спецификацией интерпретируемого ЯП является непосредственно программа на этом ЯП.
Поэтому теория формальной спецификации ЯП в основном для компилируемых ЯП.
Декларативные ЯП - в основном интерпретируемые ЯП. Соответственно формальной спецификацией программ на этих ЯП - это непосредственно сама программа.
P.S.
Если вам кажется, что где-то напиздел - пишите, будем обсуждать
Понятие алгоритма сложно формализовать.
Но есть определенные подходы - машина Тьюринга, лямда исчисление Черча, алгоритмы Маркова.
Вроде где-то доказывается, что эти подходы имеют равнозначные выразительные возможности.
И для тех или иных теоретических рассуждений нужно выбирать то, что наиболее удобно в использовании, либо придумать свой механизм элементарных вычислений. // если удастся
Чтобы задать ЯП, нужно задать его синтаксис и семантику его конструкций (кажется это называется операционная семантика ЯП).
Синтаксис задается грамматикой (контекстно свободной или контекстно зависимой - это как уж автору будет угодно)
Операционная семантика ЯП - это формальный механизм доказательства корректности программы на данном ЯП.
Т.е. должна давать ответ на вопрос - является ли данная программа корректной программой на данном ЯП.
По этой теме лучше почитать теорию. Ключевая фраза - формальная спецификация программ (или ЯП).
Для практических современных ЯП формального описания семантики вроде как не существует. Видимо по причине того, что они проектировались без учета данного понятия, так сказать по наитию авторов этих ЯП. Поэтому все материалы по формальной спецификации в основном имеют примеры с игрушечными ЯП.
Как известно, существуют компилируемые и интерпретируемые ЯП.
Формальной спецификацией интерпретируемого ЯП является непосредственно программа на этом ЯП.
Поэтому теория формальной спецификации ЯП в основном для компилируемых ЯП.
Декларативные ЯП - в основном интерпретируемые ЯП. Соответственно формальной спецификацией программ на этих ЯП - это непосредственно сама программа.
P.S.
Если вам кажется, что где-то напиздел - пишите, будем обсуждать
> Чтобы задать ЯП, нужно задать его синтаксис и семантику его конструкций (кажется это называется операционная семантика ЯП).
Существует несколько общепринятых подходов к опеределению семантики. Наиболее известными из них являются аксиоматический, операционный, денотационный, алгебраический.
Почему ты выделил операционный? Чем плоха, например, аксиоматическая или денотационная семантика?
> Операционная семантика ЯП - это формальный механизм доказательства корректности программы на данном ЯП.
Гон. Операционная семантика математически строго описывает процесс выполнения программ на данном языке. Она ничего не доказывает. Если ты хочешь что-то доказать, ты должен делать это сам. Доказательство корректности программ на данный момент делается вручную, каких-либо средств автоматизации пока не разработано.
> Т.е. должна давать ответ на вопрос - является ли данная программа корректной программой на данном ЯП.
Это совсем другое. Корректная программа - это программа, которая не делает действий, запрещенных стандартом языка. Например, не делит на нуль, не пишет в память после ее освобождения. Проверка, является ли программа корректной, по ее исходному тексту — алгоритмически неразрешимая задача.
> По этой теме лучше почитать теорию. Ключевая фраза - формальная спецификация программ (или ЯП).
Ты имеешь ввиду какие-то конкретные работы?
> Для практических современных ЯП формального описания семантики вроде как не существует.
> Видимо по причине того, что они проектировались без учета данного понятия, так сказать по
> наитию авторов этих ЯП. Поэтому все материалы по формальной спецификации в основном имеют
> примеры с игрушечными ЯП.
Опять гон. (Кстати, я достаточно часто встречаю это заблуждение — интересно, откуда оно идет?)
Имеются промышленные, широко используемые языки с полностью описанной семантикой.
Например, полное описание семантики ML — Definition of Standard ML, 2nd ed.
Формальная семантика C — A Formal Semantics for the C Programming Language.
Вот цитаты из этой работы:
''Few real languages have been given formal semantics as part of their definition. Among them one should mention Scheme [IEEE91, Abel91] and Standard ML [Miln90, Miln91, Kahr93], using denotational and operational semantics respectively. Denotational semantics have also been used for the formalization of Ada [Pede80], Algol 60 [Bjor82a], Pascal [Bjor82b], and Smalltalk-80 [Wolc87], whereas operational semantics have been used for Eiffel [Atta93] and Scheme [Hons95]. In a seminal paper, axiomatic semantics have been used to partially describe the semantics of Pascal [Hoar73]. Among other formalisms, action semantics have been used for Pascal [Moss93] and Standard ML [Watt87], and abstract state machines for Ada [Morr90], Cobol [Vale93], C++ [Wall93, Wall95], Modula-2 [Gure88, Morr88], Oberon [Kutt97b, Kutt97a], Occam [Gure90, Borg94a, Borg96], Prolog [Borg94b] and Smalltalk [Blak92].''
> Как известно, существуют компилируемые и интерпретируемые ЯП.
Это уже методы реализации. Одну и ту же семантику можно реализовать как в виде интерпретатора, так и в виде компилятора. Кроме того, имея интерпретатор, можно легко сделать компилятор. Вообще, разница между компиляцией и интерпретацией значительно меньше, чем может показаться на первый взгляд.
> Формальной спецификацией интерпретируемого ЯП является непосредственно программа на этом ЯП.
Что такое спецификация на ЯП? Спецификация на программу — понятно, а на язык?
> Декларативные ЯП - в основном интерпретируемые ЯП.
? Большинство функциональных языков — компилируемые (например, Lisp, Scheme, ML, Haskell).
Существует несколько общепринятых подходов к опеределению семантики. Наиболее известными из них являются аксиоматический, операционный, денотационный, алгебраический.
Почему ты выделил операционный? Чем плоха, например, аксиоматическая или денотационная семантика?
> Операционная семантика ЯП - это формальный механизм доказательства корректности программы на данном ЯП.
Гон. Операционная семантика математически строго описывает процесс выполнения программ на данном языке. Она ничего не доказывает. Если ты хочешь что-то доказать, ты должен делать это сам. Доказательство корректности программ на данный момент делается вручную, каких-либо средств автоматизации пока не разработано.
> Т.е. должна давать ответ на вопрос - является ли данная программа корректной программой на данном ЯП.
Это совсем другое. Корректная программа - это программа, которая не делает действий, запрещенных стандартом языка. Например, не делит на нуль, не пишет в память после ее освобождения. Проверка, является ли программа корректной, по ее исходному тексту — алгоритмически неразрешимая задача.
> По этой теме лучше почитать теорию. Ключевая фраза - формальная спецификация программ (или ЯП).
Ты имеешь ввиду какие-то конкретные работы?
> Для практических современных ЯП формального описания семантики вроде как не существует.
> Видимо по причине того, что они проектировались без учета данного понятия, так сказать по
> наитию авторов этих ЯП. Поэтому все материалы по формальной спецификации в основном имеют
> примеры с игрушечными ЯП.
Опять гон. (Кстати, я достаточно часто встречаю это заблуждение — интересно, откуда оно идет?)
Имеются промышленные, широко используемые языки с полностью описанной семантикой.
Например, полное описание семантики ML — Definition of Standard ML, 2nd ed.
Формальная семантика C — A Formal Semantics for the C Programming Language.
Вот цитаты из этой работы:
''Few real languages have been given formal semantics as part of their definition. Among them one should mention Scheme [IEEE91, Abel91] and Standard ML [Miln90, Miln91, Kahr93], using denotational and operational semantics respectively. Denotational semantics have also been used for the formalization of Ada [Pede80], Algol 60 [Bjor82a], Pascal [Bjor82b], and Smalltalk-80 [Wolc87], whereas operational semantics have been used for Eiffel [Atta93] and Scheme [Hons95]. In a seminal paper, axiomatic semantics have been used to partially describe the semantics of Pascal [Hoar73]. Among other formalisms, action semantics have been used for Pascal [Moss93] and Standard ML [Watt87], and abstract state machines for Ada [Morr90], Cobol [Vale93], C++ [Wall93, Wall95], Modula-2 [Gure88, Morr88], Oberon [Kutt97b, Kutt97a], Occam [Gure90, Borg94a, Borg96], Prolog [Borg94b] and Smalltalk [Blak92].''
> Как известно, существуют компилируемые и интерпретируемые ЯП.
Это уже методы реализации. Одну и ту же семантику можно реализовать как в виде интерпретатора, так и в виде компилятора. Кроме того, имея интерпретатор, можно легко сделать компилятор. Вообще, разница между компиляцией и интерпретацией значительно меньше, чем может показаться на первый взгляд.
> Формальной спецификацией интерпретируемого ЯП является непосредственно программа на этом ЯП.
Что такое спецификация на ЯП? Спецификация на программу — понятно, а на язык?
> Декларативные ЯП - в основном интерпретируемые ЯП.
? Большинство функциональных языков — компилируемые (например, Lisp, Scheme, ML, Haskell).
То что я привел, это скорее описание подхода к определению алгоритма, а не само формальное определение.
Формальное определение нормального алгоритма Маркова я могу привести, но оно будет не интересно.
Если ты аксиоматически описал, что выбор "какого-нибудь n" есть элементарная операция и ее сложность равна 1 (или С, или еще чему-нибудь то все будет корректно, если это не описано, то очевидно, как с формальной точки зрения, так и чисто с практической отсутствие такого пояснения будет недочетом.
Алгоритм - первоначально не процесс, а некоторый набор предписаний, определяющих процесс. Например, алгоритм заданный машиной тьюринга не всегда должен останавливаться (завершаться за конечное время).
Я думаю для того что бы формально корректно описывать алгоритмы, необходимо заранее оговорить набор допустимых элементарных операций, а также указать их предполагаемую сложность (также стоит описать сложность перехода от выполнения одной операции к другой, если этот переход не тривиален). Все алгоритмы необходимо раскладывать на элементарные операции и переходы, в соответствии с предположениями строить оценки сложности.
Такой подход в принципе независим от других формальных моделей алгоритма (машины тьюринга МТ). При этом, если это необходимо, то каждый желающий может построить модель отображающую твои элементарные операции в термины, например, МТ, затем построить оценки сложности этих операций для МТ, а затем преобразовать твои оценки в оценки сложности вычислений на МТ.
А вообще, когда я видел оценки сложности в работах (когда это не являлось каким-либо выдающимся научным результатом то там не уделяли особого внимания формальности оценок.
Некоторые предположения при описании алгоритмов являются общепринятыми, и не оговариваюся вовсе, например, если речь идет о программах на языке C.
Например, считаем, что сложение, вычитание, умножение, деление, доступ к ячейке памяти, присваивание, условный переход - выполняются за константное время (когда нужно, эти времена считаю различными). Набор операций типа ЦИКЛ также не описывается подробно.
Формальное определение нормального алгоритма Маркова я могу привести, но оно будет не интересно.
Может ли описанный таким образом метод вычислений считаться алгоритмом? Насколько строго требуется описывать процесс вычислений? Насколько допустимы в нем фразы типа "возьмем какое-нибудь n".
Если ты аксиоматически описал, что выбор "какого-нибудь n" есть элементарная операция и ее сложность равна 1 (или С, или еще чему-нибудь то все будет корректно, если это не описано, то очевидно, как с формальной точки зрения, так и чисто с практической отсутствие такого пояснения будет недочетом.
Если у нас есть метод вычислений, но не доказано, что он завершается за конечное время, то можно ли считать его алгоритмом?
Алгоритм - первоначально не процесс, а некоторый набор предписаний, определяющих процесс. Например, алгоритм заданный машиной тьюринга не всегда должен останавливаться (завершаться за конечное время).
Вообще я не вижу особого смысла привязываться к машине тьюринга.
Как трансформируется сложность при переходе от одного представления к другому - я не знаю, но вполне возможно, что сложность будет увеличиваться более чем линейно.
Формально мы можем предположить в своей модели что-угодно, в том числе и то, что сложность сложения любых чисел равна единице (это вполне распространенный случай).
Но в машине Тьюринга этого сделать нельзя, и сложность как минимум будт зависеть от длины представления этих чисел.
Я думаю для того что бы формально корректно описывать алгоритмы, необходимо заранее оговорить набор допустимых элементарных операций, а также указать их предполагаемую сложность (также стоит описать сложность перехода от выполнения одной операции к другой, если этот переход не тривиален). Все алгоритмы необходимо раскладывать на элементарные операции и переходы, в соответствии с предположениями строить оценки сложности.
Такой подход в принципе независим от других формальных моделей алгоритма (машины тьюринга МТ). При этом, если это необходимо, то каждый желающий может построить модель отображающую твои элементарные операции в термины, например, МТ, затем построить оценки сложности этих операций для МТ, а затем преобразовать твои оценки в оценки сложности вычислений на МТ.
А вообще, когда я видел оценки сложности в работах (когда это не являлось каким-либо выдающимся научным результатом то там не уделяли особого внимания формальности оценок.
Некоторые предположения при описании алгоритмов являются общепринятыми, и не оговариваюся вовсе, например, если речь идет о программах на языке C.
Например, считаем, что сложение, вычитание, умножение, деление, доступ к ячейке памяти, присваивание, условный переход - выполняются за константное время (когда нужно, эти времена считаю различными). Набор операций типа ЦИКЛ также не описывается подробно.
Ты имеешь ввиду какие-то конкретные работы?Formal.Syntax.And.Semantics.of.Programming.Language и в том же духе.
Опять гон. (Кстати, я достаточно часто встречаю это заблуждение — интересно, откуда оно идет?)
Имеются промышленные, широко используемые языки с полностью описанной семантикой.
Например, полное описание семантики ML — Definition of Standard ML, 2nd ed.
Формальная семантика C — A Formal Semantics for the C Programming Language.
Упущение. Недоговорил.
Современные импертивные языки - C, C++, Java и т.д.
Это уже методы реализации. Одну и ту же семантику можно реализовать как в виде интерпретатора, так и в виде компилятора. Кроме того, имея интерпретатор, можно легко сделать компилятор. Вообще, разница между компиляцией и интерпретацией значительно меньше, чем может показаться на первый взгляд.
Если для ЯП можно написать интерпретатор - то язык интерпретируемый
И вообще интерпретатор должен входить в стандарт языка, в качестве механизма формальной спецификации программ на этом ЯП
Что такое спецификация на ЯП? Спецификация на программу — понятно, а на язык?
Формальный синтаксис + работающий интерпертатор (либо существующая операционная/денотационная/аксиоматическая/алгебраическая семантика ЯП)
Почему ты выделил операционный? Чем плоха, например, аксиоматическая или денотационная семантика?
как основополагающая // имхо.
Операционная семантика математически строго описывает процесс выполнения программ на данном языке. Она ничего не доказывает. Если ты хочешь что-то доказать, ты должен делать это сам. Доказательство корректности программ на данный момент делается вручную, каких-либо средств автоматизации пока не разработано."Не существует" это ты на все языки обобщил ?
А как же интерпретатор языка - это разве не автоматическое средство доказательства корректности программ ?
> Если ты аксиоматически описал, что выбор "какого-нибудь n" есть элементарная операция и ее
> сложность равна 1 (или С, или еще чему-нибудь то все будет корректно, если это не описано,
> то очевидно, как с формальной точки зрения, так и чисто с практической отсутствие такого
> пояснения будет недочетом.
Конечно, можно постулировать, что абстрактная машина, на которой работает имеет такую инструкцию solve и умеет за один такт решать уравнение f(x)=0. Но с практической точки зрения непонятно, как такое вообще может быть? Единственное, что приходит на ум — сидеть и перебирать последовательно все натуральные числа. Такой способ дает правильный результат, но сложность его может быть ооочень большой. Непонятно даже, как ее оценить. Поэтому приписывать такой операции некоторое константное времени неправильно.
> Я думаю для того что бы формально корректно описывать алгоритмы, необходимо заранее оговорить
> набор допустимых элементарных операций, а также указать их предполагаемую сложность (также
> стоит описать сложность перехода от выполнения одной операции к другой, если этот переход не
> тривиален).
Как быть, если набор элементарных операций сильно разный? Например, в императивных языка есть операция "обновить ячейку памяти", а в функциональных языках — нет, зато есть операции "создать замыкание". Эти операции "идейно разные", их нельзя так просто выразить одну через другую. Как правило, при написании функциональной программы по императивной приходится существенно менять структуру данных и алгоритмы, простым переписыванием не отделаться.
> Все алгоритмы необходимо раскладывать на элементарные операции и переходы, в соответствии с
> предположениями строить оценки сложности.
+1
> сложность равна 1 (или С, или еще чему-нибудь то все будет корректно, если это не описано,
> то очевидно, как с формальной точки зрения, так и чисто с практической отсутствие такого
> пояснения будет недочетом.
Конечно, можно постулировать, что абстрактная машина, на которой работает имеет такую инструкцию solve и умеет за один такт решать уравнение f(x)=0. Но с практической точки зрения непонятно, как такое вообще может быть? Единственное, что приходит на ум — сидеть и перебирать последовательно все натуральные числа. Такой способ дает правильный результат, но сложность его может быть ооочень большой. Непонятно даже, как ее оценить. Поэтому приписывать такой операции некоторое константное времени неправильно.
> Я думаю для того что бы формально корректно описывать алгоритмы, необходимо заранее оговорить
> набор допустимых элементарных операций, а также указать их предполагаемую сложность (также
> стоит описать сложность перехода от выполнения одной операции к другой, если этот переход не
> тривиален).
Как быть, если набор элементарных операций сильно разный? Например, в императивных языка есть операция "обновить ячейку памяти", а в функциональных языках — нет, зато есть операции "создать замыкание". Эти операции "идейно разные", их нельзя так просто выразить одну через другую. Как правило, при написании функциональной программы по императивной приходится существенно менять структуру данных и алгоритмы, простым переписыванием не отделаться.
> Все алгоритмы необходимо раскладывать на элементарные операции и переходы, в соответствии с
> предположениями строить оценки сложности.
+1
>> Формальная семантика C — A Formal Semantics for the C Programming Language.
> Современные импертивные языки - C, C++, Java и т.д.
?
> Если для ЯП можно написать интерпретатор - то язык интерпретируемый
Тогда приведи пример неинтерпретируемого языка
> И вообще интерпретатор должен входить в стандарт языка, в качестве механизма формальной
> спецификации программ на этом ЯП
Вроде как считается, что в стандарт языка должна входить семантика, описанная на математическом (что предпочтительнее) или на человеческом (что хуже) языке. А включать в стандарт конкретную реализацию — зло (снижает переносимость и т.п.).
> Формальный синтаксис + работающий интерпертатор (либо существующая
> операционная/денотационная/аксиоматическая/алгебраическая семантика ЯП)
На мой взгляд, интерпретатор и семантика — сильно разные вещи. Семантика — это некоторое математическое описание, набор формул. А интерпретатор — это конкретная программа, ее можно запустить, кнопочки потыркать.
>> Почему ты выделил операционный?
> как основополагающая // имхо.
Некоторые, например N. S. Papaspyrou, считают, что операционный подход не рулит (а рулит денотационный). Есть какие-нибудь доводы в пользу твоего имхо?
> Современные импертивные языки - C, C++, Java и т.д.
?
> Если для ЯП можно написать интерпретатор - то язык интерпретируемый
Тогда приведи пример неинтерпретируемого языка
> И вообще интерпретатор должен входить в стандарт языка, в качестве механизма формальной
> спецификации программ на этом ЯП
Вроде как считается, что в стандарт языка должна входить семантика, описанная на математическом (что предпочтительнее) или на человеческом (что хуже) языке. А включать в стандарт конкретную реализацию — зло (снижает переносимость и т.п.).
> Формальный синтаксис + работающий интерпертатор (либо существующая
> операционная/денотационная/аксиоматическая/алгебраическая семантика ЯП)
На мой взгляд, интерпретатор и семантика — сильно разные вещи. Семантика — это некоторое математическое описание, набор формул. А интерпретатор — это конкретная программа, ее можно запустить, кнопочки потыркать.
>> Почему ты выделил операционный?
> как основополагающая // имхо.
Некоторые, например N. S. Papaspyrou, считают, что операционный подход не рулит (а рулит денотационный). Есть какие-нибудь доводы в пользу твоего имхо?
> "Не существует" это ты на все языки обобщил ?
Да. Языки, не являющиеся алгоритмически полными, не рассматриваем.
> А как же интерпретатор языка - это разве не автоматическое средство доказательства корректности программ ?
Не понял Интерпретатор — программа, поэтому он не может решать алгоритмически неразрешимую задачу.
Да. Языки, не являющиеся алгоритмически полными, не рассматриваем.
> А как же интерпретатор языка - это разве не автоматическое средство доказательства корректности программ ?
Не понял
Интерпретатор — программа, поэтому он не может решать алгоритмически неразрешимую задачу.> Современные импертивные языки - C, C++, Java и т.д.
?
С++, Java
Тогда приведи пример неинтерпретируемого языка
С++ ?
Некоторые, например N. S. Papaspyrou, считают, что операционный подход не рулит (а рулит денотационный). Есть какие-нибудь доводы в пользу твоего имхо?
Может потому, что операционную семантику еще называют традиционной ?
A program is correct if it does what we would like it to do.H ow can we tell whether
a program is correct? Usually it is impossible to duplicate the program’s calculation
by hand.W e need other ways. One simple way, which we used before, is to verify
that the program is correct for outputs that we know.This increases confidence in
the program.Bu t it does not go very far. To prove correctness in general, we have
to reason about the program.Th is means three things:
1. We need a mathematical model of the operations of the programming language,
defining what they should do.This model is called the language’s semantics.
2. We need to define what we would like the program to do.Usua lly, this is a
mathematical definition of the inputs that the program needs and the output that
it calculates.This is called the program’s specification.
3. We use mathematical techniques to reason about the program, using the semantics.
W e would like to demonstrate that the program satisfies the specification.
Кстати, Nikos Papaspyrou как раз использовал интерпретатор для пункта 3. // http://www.softlab.ntua.gr/~nickie/Thesis/
Но с практической точки зрения непонятно, как такое вообще может быть?
Просто стоит задаться вопросом - а зачем это все?
1. Если для строгости и формальности - то действительно надо формализовывать все элементарные операции, и никуда от этого не деться. И здесь не важно сводишь ли ты задачу к машине тьюринга, либо к некоей своей модели вычислительной машины.
2. Если это необходимо с практической точки зрения, то очевидно надо формализовывать существующую на практике вычислительную машину, а затем сводить к ее модели построенные тобой алгоритмы. Если действительно важна практическая сторона, то часть формализаций можно опустить, т.к. они очевидны и общеприняты.
А если хочется всего одновременно, то имхо придется попотеть
.Как быть, если набор элементарных операций сильно разный?
С нетривиальностью преобразований я не спорю, просто вопрос в том, нужно ли оно или нет?
Если речь идет о практической стороне, я бы сразу стал описывать алгоритмы так, чтобы они наиболее просто и очевидно отображались в термины вичислительной машины, на которой эти алгоритмы исполняются. То есть на языке подобному императивным языкам программирования. Ну если совсем в корень смотреть, то необходимо описывать алгоритмы на ассемблере. Все жа так в основном и поступают - раскладывают алгоритмы на сложения, умножения, условные переходы и циклы. С функциональными языками похуже, т.к. наверное многое зависит от его компилятора (интерпретатора, если такие есть, сорри в функциональных языках плохо соображаю).
Итак:
1. Модели вычислительных машин разные, но множества задаваемых функций одинаковые.
2. Преобразование между моделями не всегда тривиально.
3. Сложность вычислений зависит от модели, но преобразования между моделями сохраняют классы сложности P и NP.
4. Императивные языки наиболее близки к существующим на практике вычислительным машинам.
ЗЫ
Если ты описываешь алгоритм на функциональном языке и даешь его оценку сложности,
формально для того что бы говорить об оценки времени исполнения, все равно придется как-то описывать сложность его интерпретации в терминах реальной вычислительной машины (например, в терминах ассемблера). То есть в любом случае придется сослаться на какие-нибудь работы, где описываются методики как вычислить реальную сложность выполнения функциональной программы на обычном компе.
Глубина корректности так сказать
A program that is proved correct can still give incorrect results, if the system on
which it runs is incorrectly implemented.Ho w can we be confident that the system
satisfies the semantics? Verifying this is a major undertaking: it means verifying
the compiler, the run-time system, the operating system, the hardware, and the
physics upon which the hardware is based!
> А как же интерпретатор языка - это разве не автоматическое средство доказательства корректности программ ?Не понял Интерпретатор — программа, поэтому он не может решать алгоритмически неразрешимую задачу.Кстати, а можешь огласить какая именно "алгоритмически неразрешимая задача" возникает ?
Уж не "проблема применимости алгоритма" ?
Кстати, а можешь огласить какая именно "алгоритмически неразрешимая задача" возникает ?
Уж не "проблема применимости алгоритма" ?
Каждую задачу можно рассматривать как функцию (она описывает соответствие между исходными данными и результатом - решением задачи).
Множество алгоритмов в той или иной формальной постановке также задает множество функций. Но для некоторых функций не существует алгоритмов, которые их задают.
Задачи, которым соответствуют функции, которые нельзя задать каким-либо алгоритмом называют алгоритмически неразрешимыми.
То есть такие задачи берутся из того, что класс функций, задаваемый задачами шире чем класс функций задаваемых алгоритмами. Задачей можно считать любое формальное математическое описание, то есть наверное можно говорить, что класс функций, задаваемых задачами это вообще класс всевозможных функций, хотя х.з.
Боюсь, что имелось в виду другое.
А разве гипотезу Тьюринга опровергли ?
Множество алгоритмов в той или иной формальной постановке также задает множество функций. Но для некоторых функций не существует алгоритмов, которые их задают.
А разве гипотезу Тьюринга опровергли ?
Она не противоречит существованию функций,
которые невозможно описать каким-либо алгоритмом.
которые невозможно описать каким-либо алгоритмом.
т.е. это задачи для которых не нашли решений ?
тогда это точно не та проблема
тогда это точно не та проблема
Нет, это задачи, для которых доказана неразрешимость с помощью машины Тьюринга.
Не совсем понимаю, что значит задачи, для которых нет решений?
А вообще - вопрос философский, надо подумать
А вообще - вопрос философский, надо подумать
А, нашел о чем ты,
То есть это значит что мы не сможем написать такой алгоритм, который будет на вход получать программу, а на выходе давать ответ - даст ли результат эта программа на всевозможных входных данных, или не даст.
Так вот, в некоторых случаях мы можем сразу сказать - остановится ли алгоритм или нет,
в некоторых случаях мы можем доказать это и т.п.
Но алгоритма, который в общем случае решает эту задачу составить нельзя.
Простейшим примером алгоритмически неразрешимой массовой проблемы является так называемая проблема применимости алгоритма (называемая также проблемой остановки)То есть проблема остановки относится к классу неразрешимых.
То есть это значит что мы не сможем написать такой алгоритм, который будет на вход получать программу, а на выходе давать ответ - даст ли результат эта программа на всевозможных входных данных, или не даст.
Так вот, в некоторых случаях мы можем сразу сказать - остановится ли алгоритм или нет,
в некоторых случаях мы можем доказать это и т.п.
Но алгоритма, который в общем случае решает эту задачу составить нельзя.
Видимо дело в том, что понятие корректности программы на ЯП и на машине Тьюринга несколько отличаются
Либо множество машин Тьюринга порождаемые семантикой ЯП входит в эти самые некоторые случаи.
Ведь у компьютера нет бесконечной памяти
Либо множество машин Тьюринга порождаемые семантикой ЯП входит в эти самые некоторые случаи.
Ведь у компьютера нет бесконечной памяти
Каждую задачу можно рассматривать как функцию (она описывает соответствие между исходными данными и результатом - решением задачи).
Множество алгоритмов в той или иной формальной постановке также задает множество функций. Но для некоторых функций не существует алгоритмов, которые их задают.
Задачи, которым соответствуют функции, которые нельзя задать каким-либо алгоритмом называют алгоритмически неразрешимыми.
Кстати, чем функции в твоем случае отличаются от функций в лямбда исчислении Черча ?
Лямбда исчисление вроде как сводится к машинам Тьюринга.
Лямбда-исчисление как-то косвенно к МТ сводится. Там выделяются особые термы n*, к-рые обозначают числа, и говорят, что ф-я f представима в лямда-исчислении термом f*, если f*n* редуцируется к (f(n*. (могу что-то перепутать)
Кстати, чем функции в твоем случае отличаются от функций в лямбда исчислении Черча ?
Лямбда исчисление вроде как сводится к машинам Тьюринга.
В моем понимании функция - это отображение одного множества в другое, без относительно способа задания или описания.
Функция в лямбда-исчислении это некоторая запись, описывающая функцию в соответствии с определенными правилами. (отсюда и проблема, что при помощи лямбда исчисления или другого формального подхода к понятию алгоритм можно задать не всякую функцию)
Для лямбда исчисления, машин тьюринга и нормальных алгоритмов маркова доказана эквивалентность классов функций, которые можно ими задать. На счет вопроса, что одна модель сводится к другой - все зависит от того, что ты понимаешь под словом "сводится".
а что это за классы функций ?
Это точно неверно. Попробуй построить конечный автомат для сортировки N чисел в массиве.Да. Тут, по-моему, уже говорили, но я еще раз скажу:
действительно, такой автомат строить я не возьмусь. Я могу построить автомат для сортировки N чисел в массиве при N<=M, M <- N.
Не раскрыта тема остановки. Ну, вот там где ты говоришь про "область конечных состояний автомата", ты неявно очень страшные и могучие вещи подтягиваешь.А что в них страшного?
У автомата есть подмножество состояний Fini, из которых не выходит ни одна дуга.
В этом подмножетсве есть белое и пушистое подмножество (БПП элементы которого хорошо подходят для рекламных скриншотов.
Все элементы (Fini - БПП) на форумах получают зловещие и звучные имена "BSOD", "coredump" etc.
Разве не так?
Вопрос заключается в том, что значит строго определенные правила?Предложения на языке программирования, которые соответствуют переходам (путям) в автомате.
Например, один из шагов может формулироваться так: "Шаг 17. В переменную X записывается какое-нибудь решение уравнения f(x) = 0". При этом не говорится, как это уравнение решать, и какой именно корень следует выбирать, если их много.Гм. Вообще, как я понимаю, это будет подпрограмма: (1/f0) считается тоже алгоритмически (если оператор ушел на обед, а оракул третий день в запое).
Все функции, как правило, считаются аппроксимациями, которые в императивном подходе в конечном итоге сводящимися к арифметике, чтениям-загрузкам и переходам. Алгоритмы для элементарных арифметических действий рассказываются еще в начальной школе (это именно алгоритмы переписывания строк чисел, ничего иного там не придумали, их правда можно еще как-нибудь хитро реализовывать, сказал я себе, узнав про FFT-умножение).
Остальные варианты в терминах состояний алгоритма записываются явно.
В лямбда-случае еще проще: все шаги алгоритма - это преобразования строки по правилам редукции.
Другой вариант. "Шаг 18. Выберем какое-нибудь натуральное n. Проведем шаги 19-45. Если шаге 45 получилась лажа, вернуться в шаг 18, попробовать какое-нибудь другое натуральное n" (опять не указывается как его выбирать, и сколько раз нужно повторять все это).Гы. "Как выбирать" - это, по-моему, главный вопрос при взломе крипто-алгоритма, а "сколько повторять" - это тема для оценки в серьезной научной работе, если не ошибаюсь.
Может ли описанный таким образом метод вычислений считаться алгоритмом?Угу. Когда разработан формальный язык вплоть до символов и элементарных преобразований, алгоритмом может считаться все, что можно строго расписать.
Насколько допустимы в нем фразы типа "возьмем какое-нибудь n".Implementation-dependent.
Если у нас есть метод вычислений, но не доказано, что он завершается за конечное время, то можно ли считать его алгоритмом?Хм. Есть лямбда-выраждения, приводящие к бесконечной редукции (примеры для ограниченной и неограниченно растущей длины строки элементарны).
Алгоритмом нельзя считать только то, что полезно в хозяйстве. Но если хочется, то сперва, мне кажется, надо ответить на более определенный вопрос: если метод вычислений для конкретной строки ввода не завершится никогда, можно ли его считать алгоритмом?
Тот же самый вопрос: если на некотором шаге указывается несколько возможных путей выполнения, но не указывается какой именно следует из них выбирать, то является ли такой метод вычисления алгоритмом?Э-э-э, если не указано, то это уже недетерминистская машина, так?
Кстати на счет конечного автомата и т.п., машина тьюринга похожа по своему определению на конечный автомат, но всеже является его расширением.Ладно. Тогда автоматной функцией является физически реализуемый алгоритм, т.е. такой, который в нашей Вселенной вообще можно выполнить.
Множество автоматных функций является подмножеством множества вычислимых функций.
Не раскрыта тема вычислительной сложности алгоритма. Если бы ты сходил по моей ссылочге и потыкал в разные места, то увидел бы, что большинство классов подразумевает сильно подпатченную машину Тьюринга и специфические критерии оценки ответа.Как связано формальное определение алгоритма и его сложность? Сложности я даже не касался.
Кстати, а что будем делать с невычислимыми функциями?А что с ними можно сделать? Невычислимые функции к теории алгоритмов имеют вполне прозрачное отношение: они к ней не относятся (еще иногда в ней появляются, но это уже отношения другого уровня).
Чтобы что-то сделать с невычислимой функцией, тебе надо написать гипералгоритм.
Только раздел поменяли на Development, как разгорелся такой красивый теоретический флуд.
а что это за классы функций ?
Т.к. классы эквивалентны (ну в смысле равны то в итоге это один класс - алгоритмически вычислимых функций.
У автомата есть подмножество состояний Fini, из которых не выходит ни одна дуга.Но можешь ли ты в них попасть? Вот в чём вопрос...
И хватит уже говорить про автоматы, машина Тьюринга — это не автомат, это автомат с лентой или двумя стеками.
> ...
Если ты не заметил, тут обсуждаются именно алгоритмы с привязкой к вычислительной сложности. И понятно почему: если на неё забить, то тезиса Тьюринга-Чёрча хватает полностью на всё.
2All: чтоб вам не казалось, что проблема остановки автомата это какая-то фигня, интересная только с теоретической точки зрения, могу подкинуть ещё примерчег невычислимой функции, называется "Busy Beaver", формулируется так: S(n) = максимальное количество единиц, которое выводится машиной Тьюринга с n состояниями и двумя символами в алфавите, с начальной лентой заполненной нулями. Останавливающейся, естественно. В данный момент задача решена только для n = 4 (четырём для n = 5 текущий лидер даёт 4098 единиц за 47,176,870 итераций. Внушает, по-моему.
> Кстати, а можешь огласить какая именно "алгоритмически неразрешимая задача" возникает ?
> Уж не "проблема применимости алгоритма" ?
Рассмотрим такую программу:
void shit_function
{
// сделать какую-нибудь лажу, например
*(int*)0 = 0;
}
int main
{
if (хитрожопое_выражение != 0) {
shit_function;
} else {
return правильный_ответ;
}
}
Эта программа корректна тогда и только тогда, когда "хитрожопое_выражение" равно 0.
Задача определения корректности этой программы приводит к определению того, дает ли вычисление некоторого выражения 0. А эта задача является алгоритмически неразрешимой (она эквивалентна проблеме применимости алгоритма).
> Уж не "проблема применимости алгоритма" ?
Рассмотрим такую программу:
void shit_function
{
// сделать какую-нибудь лажу, например
*(int*)0 = 0;
}
int main
{
if (хитрожопое_выражение != 0) {
shit_function;
} else {
return правильный_ответ;
}
}
Эта программа корректна тогда и только тогда, когда "хитрожопое_выражение" равно 0.
Задача определения корректности этой программы приводит к определению того, дает ли вычисление некоторого выражения 0. А эта задача является алгоритмически неразрешимой (она эквивалентна проблеме применимости алгоритма).
> С++, Java
Читай внимательнее:
''Few real languages have been given formal semantics ....
... and abstract state machines for Ada [Morr90], Cobol [Vale93], C++ [Wall93, Wall95], Modula-2 [Gure88, Morr88], Oberon [Kutt97b, Kutt97a], Occam [Gure90, Borg94a, Borg96], Prolog [Borg94b] and Smalltalk [Blak92].''
> Может потому, что операционную семантику еще называют традиционной
Я читал много работ по семантике, но нигде такого термина не видел. Можешь привести какую-нибудь ссылку? Есть "natural semantics", но это другое.
Читай внимательнее:
''Few real languages have been given formal semantics ....
... and abstract state machines for Ada [Morr90], Cobol [Vale93], C++ [Wall93, Wall95], Modula-2 [Gure88, Morr88], Oberon [Kutt97b, Kutt97a], Occam [Gure90, Borg94a, Borg96], Prolog [Borg94b] and Smalltalk [Blak92].''
> Может потому, что операционную семантику еще называют традиционной
Я читал много работ по семантике, но нигде такого термина не видел. Можешь привести какую-нибудь ссылку? Есть "natural semantics", но это другое.
> A program is correct if it does what we would like it to do.H ow can we tell ...
Корректность можно понимать в двух смыслах.
1. Есть некоторая спецификация. Программа корректна, если она соответствует этой спецификации.
2. Спецификации нет. Программа считается корректной, если она завершается за конечное время и не делает действий, запрещенных правилами языка (например, не лезет в освобожденную память). Результат работы при этом не важен.
Корректность1 != Корректность2. Это разные понятия.
Проверка обоих представляет собой алгоритмически неразрешимую задачу.
Корректность можно понимать в двух смыслах.
1. Есть некоторая спецификация. Программа корректна, если она соответствует этой спецификации.
2. Спецификации нет. Программа считается корректной, если она завершается за конечное время и не делает действий, запрещенных правилами языка (например, не лезет в освобожденную память). Результат работы при этом не важен.
Корректность1 != Корректность2. Это разные понятия.
Проверка обоих представляет собой алгоритмически неразрешимую задачу.
> С нетривиальностью преобразований я не спорю, просто вопрос в том, нужно ли оно или нет?
> Если речь идет о практической стороне, я бы сразу стал описывать алгоритмы так, чтобы они
> наиболее просто и очевидно отображались в термины вичислительной машины, на которой эти
> алгоритмы исполняются. То есть на языке подобному императивным языкам программирования.
Допустим поставлена такая задача:
Дано: алгоритм, описанный в традиционном виде (например на некотором псевдокоде и некоторый функциональный язык (например, Haskell).
Надо: реализовать этот алгоритм на этом языке.
Желательно: сохранить временную сложность алгоритма.
Как решать такую задачу?
> Итак:
> 1. Модели вычислительных машин разные, но множества задаваемых функций одинаковые.
> 2. Преобразование между моделями не всегда тривиально.
> 3. Сложность вычислений зависит от модели, но преобразования между моделями сохраняют классы
> сложности P и NP.
> 4. Императивные языки наиболее близки к существующим на практике вычислительным машинам.
+1. Четкие формулировки.
> Если ты описываешь алгоритм на функциональном языке и даешь его оценку сложности,
> формально для того что бы говорить об оценки времени исполнения, все равно придется как-то
> описывать сложность его интерпретации в терминах реальной вычислительной машины (например, в
Допустим у меня есть функциональный язык и две различные его реализации. Время исполнения программы на одной имеет одну асимптотику, на другой другую (такое реально бывает на практике, например, если компилятор оптимизирующий). Что в таком случае можно сказать? На мой взгляд, в этом случае одна программа приводит к двум разным алгоритмам.
> Если речь идет о практической стороне, я бы сразу стал описывать алгоритмы так, чтобы они
> наиболее просто и очевидно отображались в термины вичислительной машины, на которой эти
> алгоритмы исполняются. То есть на языке подобному императивным языкам программирования.
Допустим поставлена такая задача:
Дано: алгоритм, описанный в традиционном виде (например на некотором псевдокоде и некоторый функциональный язык (например, Haskell).
Надо: реализовать этот алгоритм на этом языке.
Желательно: сохранить временную сложность алгоритма.
Как решать такую задачу?
> Итак:
> 1. Модели вычислительных машин разные, но множества задаваемых функций одинаковые.
> 2. Преобразование между моделями не всегда тривиально.
> 3. Сложность вычислений зависит от модели, но преобразования между моделями сохраняют классы
> сложности P и NP.
> 4. Императивные языки наиболее близки к существующим на практике вычислительным машинам.
+1. Четкие формулировки.
> Если ты описываешь алгоритм на функциональном языке и даешь его оценку сложности,
> формально для того что бы говорить об оценки времени исполнения, все равно придется как-то
> описывать сложность его интерпретации в терминах реальной вычислительной машины (например, в
Допустим у меня есть функциональный язык и две различные его реализации. Время исполнения программы на одной имеет одну асимптотику, на другой другую (такое реально бывает на практике, например, если компилятор оптимизирующий). Что в таком случае можно сказать? На мой взгляд, в этом случае одна программа приводит к двум разным алгоритмам.
> В моем понимании функция - это отображение одного множества в другое, без относительно способа
> задания или описания.
Вроде как в математике функция из X в Y определяется как подмножество F декартового произведения F \subset XxY, такое что (x,y_1) \in F и (x,y_2) \in F => y_1 = y_2. Во всяком случае нас на мехмате так учили.
Разве сейчас где-то используются какие-то другие определения функции?
> задания или описания.
Вроде как в математике функция из X в Y определяется как подмножество F декартового произведения F \subset XxY, такое что (x,y_1) \in F и (x,y_2) \in F => y_1 = y_2. Во всяком случае нас на мехмате так учили.
Разве сейчас где-то используются какие-то другие определения функции?
> В моем понимании функция - это отображение одного множества в другое, без относительно способа
> задания или описания.
Вроде как в математике функция из X в Y определяется как подмножество F декартового произведения F \subset XxY, такое что (x,y_1) \in F и (x,y_2) \in F => y_1 = y_2. Во всяком случае нас на мехмате так учили.
Определение правильное, под функцией я имел ввиду тоже самое, только сказал не формально.
Фишка такого определения, что с формальной точки зрения функция задана. Но на практике это не дает нам способа нахождения значения. Это я и хотел сказать.
В то же время, алгоритм именно описывает способ получения значения функции (посредством выполнения заранее оговоренных элементарных операций).
Учитывая желание 'сохранить временную сложность алгоритма' имхо такая задача не имеет решения в общем виде.
Допустим поставлена такая задача:
Дано: алгоритм, описанный в традиционном виде (например на некотором псевдокоде и некоторый функциональный язык (например, Haskell).
Надо: реализовать этот алгоритм на этом языке.
Желательно: сохранить временную сложность алгоритма.
Как решать такую задачу?
Меня опять подводит неважное знание функциональных языков, но неужели не существует простых примеров, когда сложность решения задачи на функциональном языке и к примеру на машине тьюринга имеют разные ассимптотики?
Если смотретьь не на конкретные три модели алгоритмов, а на все возможные, очевидно, что можно предложить такую модель, в которую нельзя будет отобразить алгоритм из другой модели с сохранением сложности - достаточно просто аксиоматически задать сложность какой-либо операции.
Допустим у меня есть функциональный язык и две различные его реализации. Время исполнения программы на одной имеет одну асимптотику, на другой другую (такое реально бывает на практике, например, если компилятор оптимизирующий). Что в таком случае можно сказать? На мой взгляд, в этом случае одна программа приводит к двум разным алгоритмам.
Согласен:
Сначала у тебя был алгоритм для некоей виртуальной вычислительной машины, а затем ты его преобразовал двумя способами к терминам другой вычислительной машины. В идеале функция. которую задавали все три алгоритма одна и таже, но алгоритмы разные. Разные алгоритмы имеют разную ассимптотику - тоже логично.
Вроде как в математике функция из X в Y определяется как подмножество F декартового произведения F \subset XxY, такое что (x,y_1) \in F и (x,y_2) \in F => y_1 = y_2. Во всяком случае нас на мехмате так учили.
Разве сейчас где-то используются какие-то другие определения функции?
Это теоретико-множественное определение, есть еще конструктивисты, которые считают что функция должна быть вычислимой,
или должен существовать алгоритм построения Y по X.
> А эта задача является алгоритмически неразрешимой (она эквивалентна проблеме применимости алгоритма).
Неразрешимые задачи появляются только при использовании бесконечности.
Но реальный мир можно считать конечным, а на конечом мире всегда работает алгоритм полного перебора...
имхо, от этого и стоит плясать: что в самом плохом случае мы приняем алгоритм перебора, в более удачых случаях применяем аналитику и эвристику.
Неразрешимые задачи появляются только при использовании бесконечности.
Но реальный мир можно считать конечным, а на конечом мире всегда работает алгоритм полного перебора...
имхо, от этого и стоит плясать: что в самом плохом случае мы приняем алгоритм перебора, в более удачых случаях применяем аналитику и эвристику.
Неразрешимые задачи появляются только при использовании бесконечности.не согласен.
такие задачи уже давно возникли, когда для решения оных требуется пару тысяч лет, используя все вычислительные ресурсы на Земле.
все конечно, но слишком долго (проблемы взлома криптосистем, задача факторизации и тд;)
вот это (на практике) уже и можно называть неразрешимыми проблемами ;=)
Но можешь ли ты в них попасть? Вот в чём вопрос...Это не вопрос, это хальтинг-проблема.
И хватит уже говорить про автоматы, машина Тьюринга — это не автомат, это автомат с лентой или двумя стеками.Любая машина Тьюринга, которую построили со времен Эратосфена, может быть заменена конечным автоматом.
Любая практическая задача, которую решат до наступления эпохи гипервычислений, может быть заменена конечным автоматом.
"Конечный автомат" не значит "детерминированный конечный автомат".
Я объявляю машину автоматом, в котором из каждого состояния выходит несколько дуг, из которых нужная выбирается в зависимости от символа на ленте. 
Время исполнения программы на одной имеет одну асимптотику, на другой другую (такое реально бывает на практике, например, если компилятор оптимизирующий). Что в таком случае можно сказать? На мой взгляд, в этом случае одна программа приводит к двум разным алгоритмам.Ты дополняешь понятие алгоритма свойством сложности.
Тьюринг сотоварищи изучали вопрос принципиальной возможности вычисления функций.
Твой взгляд таков, что алгоритмом следует считать некоторый метод вычисления вычислимой функции, а не произвольный.
Неразрешимые задачи появляются только при использовании бесконечности.Иди ботать матчасть про алгоритмически неразрешимые задачи и проблему останова.
Хотя в чем-то ты прав, ибо бесконечность тут имеется - количество различных входов алгоритма бесконечно.
> Иди ботать матчасть про алгоритмически неразрешимые задачи и проблему останова.
во всех видах теорем о проблеме останова используется бесконечность: либо в виде бесконечно малых, либо в виде бесконечно больших.
во всех видах теорем о проблеме останова используется бесконечность: либо в виде бесконечно малых, либо в виде бесконечно больших.
Теорема. Не существует алгоритма (то бишь машины Тьюринга который бы по данной записи кода машины Тьюринга определял останавливается она на данном входе или нет.
Где тут бесконечность?
Где тут бесконечность?
Неразрешимые задачи появляются только при использовании бесконечности.Лолнег. Я уже приводил пример Busy Beaver (см. википедия пальцем покажи, где там бесконечность.
Но реальный мир можно считать конечным, а на конечом мире всегда работает алгоритм полного перебора...
определение машины тьюринга начинается со слов:
есть бесконечная лента...
есть бесконечная лента...
> Лолнег. Я уже приводил пример Busy Beaver (см. википедия пальцем покажи, где там бесконечность.
если лента была бы конечной, то задача останова бы не стояла.
если лента была бы конечной, то задача останова бы не стояла.
Наиболее адекватное определение алгоритма - это машина Тьюринга, то есть уже введен твой бесконечный объект. Поэтому фраза
Неразрешимые задачи появляются только при использовании бесконечности.по отношении к алгоритмам выглядит по меньшей мере странно.
если лента была бы конечнойто это был бы не алгоритм, а конечный автомат.
Всего терда не читал
Алгоритм-точные последовательные указагия, приводящие к правильному решению задачи.
В школе так учили.
Алгоритм-точные последовательные указагия, приводящие к правильному решению задачи.
В школе так учили.
И ты конечно считаешь, что с таким определением можно пытаться изучать какие-то свойства алгоритмов ?
точность и последовательность
И ты конечно считаешь, что с таким определением можно пытаться изучать какие-то свойства алгоритмов ?Я ни на что не претендую с данным определением, но алгоритм может быть не обязательно компьютерным, поэтому оно на мой взгляд очень даже неплохое: ничего не добавишь, оставляя оный универсальным, и не выкинешь, не лишая данное определение описаний каких-либо характерных для алгоритма признаков.
ПОвторяю: не факт, что оно универсальное и что нет лучшего определения.
твое определение удобно еще и тем, что его можно приводить человеку, который не в курсе про машины Тьюринга, который не хочет исследовать свойства алгоритмов, но который хочет понять, о чем вообще идет речь.
> Лолнег. Я уже приводил пример Busy Beaver (см. википедия пальцем покажи, где там бесконечность.Ты, наверное, не очень хорошо понимаешь, что там происходит. Приходила ли тебе в голову такая простая мысль: машина Тьюринга, проработавшая N ходов, не может изменить/учесть что-нибудь вне куска ленты -N..N? Там нигде же не возникает настоящей бесконечности, всё кругом конечное, но как-то так получается, что если мт с четыремя состояниями не остановилась за двадцать тысяч ходов, то она не остановится уже никогда, и это можно доказать сугубо математически, опять же не аппелируя к "бесконечности".
если лента была бы конечной, то задача останова бы не стояла.
Вообще слово "бесконечность" нехорошее, и появляется как правило из-за математической неграмотности говорящего. Правильно говорить не "существует бесконечное количество простых чисел", а "для любого числа N можно найти простое число M, большее N". В этом утверждении нет никаких бесконечностей.
> что если мт с четыремя состояниями не остановилась за двадцать тысяч ходов, то она не остановится уже никогда, и это можно доказать сугубо математически, опять же не аппелируя к "бесконечности".
она остановится как дойдет до конца
она остановится как дойдет до конца
> В этом утверждении нет никаких бесконечностей.
конечно, есть.
это утверждение опирается на то, что ряд натуральных чисел бесконечен.
если бы ряд натуральных чисел кончался бы, например, на 10-ке, то для 8 никаких простых чисел, которые больше, уже бы не было.
конечно, есть.
это утверждение опирается на то, что ряд натуральных чисел бесконечен.
если бы ряд натуральных чисел кончался бы, например, на 10-ке, то для 8 никаких простых чисел, которые больше, уже бы не было.
> если мт с четыремя состояниями не остановилась за двадцать тысяч ходов, то она не остановится уже никогда, и это можно доказать сугубо математически, опять же не аппелируя к "бесконечности".
лол.
я знаю алгоритм, который методом деления пополам может остановиться в любой точке конечного куска ленты,
лень его расписывать, но кол-во состояний в нем, вроде, не больше 4.
лол.
я знаю алгоритм, который методом деления пополам может остановиться в любой точке конечного куска ленты,
лень его расписывать, но кол-во состояний в нем, вроде, не больше 4.
+1
2: предлагаешь все доказывать с помощью примитивно-рекурсивной арифметики (ботать основания математики) ?
2: предлагаешь все доказывать с помощью примитивно-рекурсивной арифметики (ботать основания математики) ?
> 2: предлагаешь все доказывать с помощью примитивно-рекурсивной арифметики (ботать основания математики) ?
Где я это предлагал? это ты сейчас это предлагаешь.
Для начала стоит разобраться зачем в математике вводится бесконечность...
Бесконечность вводится лишь по одной причине: ради однородности. т.к. в условиях бесконечности можно считать, что окрестность числа X ни чем не отличается от окрестности числа Y.
все это лишь нужно для того, чтобы упростить вывод утверждений.
кто сказал, что нынешней математике/информатике для успешной работы до сих пор нужен такой костыль?
Где я это предлагал? это ты сейчас это предлагаешь.
Для начала стоит разобраться зачем в математике вводится бесконечность...
Бесконечность вводится лишь по одной причине: ради однородности. т.к. в условиях бесконечности можно считать, что окрестность числа X ни чем не отличается от окрестности числа Y.
все это лишь нужно для того, чтобы упростить вывод утверждений.
кто сказал, что нынешней математике/информатике для успешной работы до сих пор нужен такой костыль?
Итак, опять подвожу итоги:
1. Есть общие (метафизические
) понятия алгоритма - соответствуют интуитивным представлениям человека.
В любом случае это понятие описывает процесс получения результата из исходных условий, посредством выполнения элементарных действий, возможность выполнения которых считается очевидной.
2. Есть математические модели алгоритмов, которые были перечислены ранее.
Также как и метафизический алгоритма, мат. модели задают зависимость результата от исходных данных, т.е. формально они задают некоторые функции. Классы функций, задаваемых всеми существующими мат. моделями алгоритмов эквивалентны.
Комментарий: Иногда в треде бывает так, что мы говорим об алгоритме в метафизическом смысле, а пытаемся изучать его математические свойства - надо следить о чем идет речь. Очевидно, без формального определения математического объекта вы не сможете вывести никаких свойств.
3. Для описанных ранее всевозможных определений алгоритмов интересны следующие задачи:
а) Задача определения сложности алгоритма.
б) Задача о том, как зависит сложность алгоритмов реализующих одну и туже функцию в различных моделях. Ответ - сохраняются классы P, NP, что-либо более полезное здесь не выяснили. Задача построения алгоритма одной модели по алгоритму другой модели нетривиальна и каких-либо простых для понимания и существенных результатов я не знаю, в этой теме мы их также не обсуждали.
в) Существуют ли проблемы аналогичные проблеме неразрешимости для задач про МТ с конечной лентой. Ответ - нет.
Комментарий:
а) МТ с конечным количеством состояний превращается в детерминированный автомат (Лента + состояние машины в точности задает переход к другой паре (лента;состояние МТ) При этом таких пар конечное число). Задача останова и прочие приведенные в этом треде, очевидно не сложно решаются для такого автомата.
б) Отсюда и выводы про бесконечность (называйте это как хотите, но сути это не изменит) в доказательствах про МТ - если бы она была там не нужна, то можно было бы все доказать про МТ с конечной лентой, а это не верно.
1. Есть общие (метафизические
) понятия алгоритма - соответствуют интуитивным представлениям человека. В любом случае это понятие описывает процесс получения результата из исходных условий, посредством выполнения элементарных действий, возможность выполнения которых считается очевидной.
2. Есть математические модели алгоритмов, которые были перечислены ранее.
Также как и метафизический алгоритма, мат. модели задают зависимость результата от исходных данных, т.е. формально они задают некоторые функции. Классы функций, задаваемых всеми существующими мат. моделями алгоритмов эквивалентны.
Комментарий: Иногда в треде бывает так, что мы говорим об алгоритме в метафизическом смысле, а пытаемся изучать его математические свойства - надо следить о чем идет речь. Очевидно, без формального определения математического объекта вы не сможете вывести никаких свойств.
3. Для описанных ранее всевозможных определений алгоритмов интересны следующие задачи:
а) Задача определения сложности алгоритма.
б) Задача о том, как зависит сложность алгоритмов реализующих одну и туже функцию в различных моделях. Ответ - сохраняются классы P, NP, что-либо более полезное здесь не выяснили. Задача построения алгоритма одной модели по алгоритму другой модели нетривиальна и каких-либо простых для понимания и существенных результатов я не знаю, в этой теме мы их также не обсуждали.
в) Существуют ли проблемы аналогичные проблеме неразрешимости для задач про МТ с конечной лентой. Ответ - нет.
Комментарий:
а) МТ с конечным количеством состояний превращается в детерминированный автомат (Лента + состояние машины в точности задает переход к другой паре (лента;состояние МТ) При этом таких пар конечное число). Задача останова и прочие приведенные в этом треде, очевидно не сложно решаются для такого автомата.
б) Отсюда и выводы про бесконечность (называйте это как хотите, но сути это не изменит) в доказательствах про МТ - если бы она была там не нужна, то можно было бы все доказать про МТ с конечной лентой, а это не верно.
Итог номер 1 не существует. Нет такого понимания понятия алгоритм. У каждого человека такое понимание разное. У алкоголика это алогоритм открутить-закрутить крышку-получишь водку. У физика - это включить в розетку - получишь свет.
Комментарий а) странный. пар (лента, состояние) бесконечно, потому что лента бесконечная. Проверить простоту любого натурального числа можно машиной Тьюринга, но нельзя конечным автоматом.
Комментарий а) странный. пар (лента, состояние) бесконечно, потому что лента бесконечная. Проверить простоту любого натурального числа можно машиной Тьюринга, но нельзя конечным автоматом.
все это лишь нужно для того, чтобы упростить вывод утверждений.А зачем математике отказываться от такого понятия как бесконечность, если оно облегчает жизнь. Тем более все бесконечности в математике формально определяются через другие понятия. Конечно, можно в каждом доказательстве писать "для любого N найдется M> N, такое что...", но проще написать "предел функции на бесконечности равен ...". И всем будет все понятно.
кто сказал, что нынешней математике/информатике для успешной работы до сих пор нужен такой костыль?
Польза от математики и алгоритмов как раз в том, что каким-либо конечным описанием (теоремой или алгоритмом) мы позволяем решать бесконечный набор задач (можно сказать, что мы позволяем решать произвольную задачу, чтобы не использовать этого слова, но суть от этого не изменится).
На самом деле не хотел утверждать, что общее понятие для всех одно - заменил на множественное число.
согласен 
бесконечность нужна. это не костыль. костыль - это программисты.
бесконечность нужна. это не костыль. костыль - это программисты.
Бесконечность --- это не просто понятие, облегчающее вывод. Неверующих, особенно 'я, еще раз отсылаю на основания математики, опровержение программы Гильберта, теорему Геделя, арифметику второго порядка и примитивно-рекурсивную арифметику (PRA). скорее всего влез в эту тему сам того не понимая, и продолжает непонимать, почему я об этом начал писать.
Насчет алгоритмов.
1. Если задача ставится в общем виде (то есть фактически имеем класс задач то _единый_ алгоритм должен позволять решать все эти задачи. В случае с конечными автоматами это не так. Как раз хороший пример --- класс задач "анализ любого натурального числа на простоту".
2. Как понятие алгоритм соотносится с понятием реализация алгоритма на заданном ЯП ? Скорее всего соотносится довольно слабо, да и нет смысла проводить такие связи, пока мы не сравниваем различные алгоритмы друг с другом. В любом случае это --- совсем отдельная песня, тут еще многое зависит от языка программирования. И может быть даже отличная тема для диссера.
3. Алгоритмы можно сравнивать с точки зрения сложности, но это не имеет смысла, пока не уточнено формальное понятие об алгоритме. Это кстати необязательно должна быть машина Тьюринга, поскольку можно мерить сложность в каких-то стандартных операциях, например, в операциях умножения-деления вещественных чисел. При этом всегда предполагается (хотя бы неявно) некоторое заданное, но формальное определение алгоритма.
Насчет алгоритмов.
1. Если задача ставится в общем виде (то есть фактически имеем класс задач то _единый_ алгоритм должен позволять решать все эти задачи. В случае с конечными автоматами это не так. Как раз хороший пример --- класс задач "анализ любого натурального числа на простоту".
2. Как понятие алгоритм соотносится с понятием реализация алгоритма на заданном ЯП ? Скорее всего соотносится довольно слабо, да и нет смысла проводить такие связи, пока мы не сравниваем различные алгоритмы друг с другом. В любом случае это --- совсем отдельная песня, тут еще многое зависит от языка программирования. И может быть даже отличная тема для диссера.
3. Алгоритмы можно сравнивать с точки зрения сложности, но это не имеет смысла, пока не уточнено формальное понятие об алгоритме. Это кстати необязательно должна быть машина Тьюринга, поскольку можно мерить сложность в каких-то стандартных операциях, например, в операциях умножения-деления вещественных чисел. При этом всегда предполагается (хотя бы неявно) некоторое заданное, но формальное определение алгоритма.
> зачем математике отказываться от такого понятия как бесконечность, если оно облегчает жизнь
зачем физике отказываться от физики Ньютона, и вводить сложную физику относительности, если физики Ньютона намного больше облегчает жизнь?
ответ: для того, чтобы теория лучше отражала практику
> Конечно, можно в каждом доказательстве писать "для любого N найдется M> N, такое что...",
могу еще раз повторить, что это утверждение тоже использует бесконечность (см. мой ответ _FJ)
зачем физике отказываться от физики Ньютона, и вводить сложную физику относительности, если физики Ньютона намного больше облегчает жизнь?
ответ: для того, чтобы теория лучше отражала практику
> Конечно, можно в каждом доказательстве писать "для любого N найдется M> N, такое что...",
могу еще раз повторить, что это утверждение тоже использует бесконечность (см. мой ответ _FJ)
> скорее всего влез в эту тему сам того не понимая, и продолжает непонимать, почему я об этом начал писать.
О, Великий Гуру развей, пожалуйста, мое невежество, и покажи на пальцах что именно я не понимаю.
ps
я смотрю дальше, чем твои отсылки к началам, и утверждаю, что все тоже самое дерево математики можно построить и на конечных последовательностях (а не только бесконечных)
О, Великий Гуру развей, пожалуйста, мое невежество, и покажи на пальцах что именно я не понимаю.
ps
я смотрю дальше, чем твои отсылки к началам, и утверждаю, что все тоже самое дерево математики можно построить и на конечных последовательностях (а не только бесконечных)
Я, возможно, чего то не понял, но как соотнести твое утверждение, допустим, с тем, что аксиома бесконечности независима от остальных аксиом теории мн-в Цермело?
развей, пожалуйста, мое невежествоЕсли ты этого так хочешь, то определи формально понятие "построить на конечных последовательностях".
Я, возможно, чего то не понял, но как соотнести твое утверждение, допустим, с тем, что аксиома бесконечности независима от остальных аксиом теории мн-в Цермело?некорректная постановка вопроса
зачем физике отказываться от физики Ньютона, и вводить сложную физику относительности, если физики Ньютона намного больше облегчает жизнь?
ответ: для того, чтобы теория лучше отражала практику
Еще раз повторю свою мысль, что бесконечность от которой ты предлагаешь отказаться по сути есть условное обозначение математического понятия. Именно из этого следовало написанное мной утверждение. Каким образом отказ от одного условного обозначения и замена его на другое может повлиять на суть проблемы ты так и не объяснил.
Очевидно в твоем примере неверна посылка, следовательно и приведенное следствие тоже не верно.
могу еще раз повторить, что это утверждение тоже использует бесконечность (см. мой ответ _FJ)
Использует, и что с того?
Ты пока что не привел ни одного утверждения, которое бесконечности не использует.
Любое универсальное утверждение или алгоритм будет использовать понятие бесконечности.
Если смотреть на твой "алгоритм", то он позволяет применять себя для любого числа и для любого отрезка, коих бесконечно много, а следовательно использует понятие бесконечности также как и утверждение про предел (из-за квантора "для любого"). В конце-концов даже для того, чтобы задать число тебе придется для каждого числа хранить достаточно большое количество информации.
Более того, пример про алгоритм деления отрезка несостоятелен, т.к. пример этот метафизический, поскольку не базируется ни на формальных определениях алгоритма, ни на какой-либо реализованной вычислительной машине.
утверждаю, что все тоже самое дерево математики можно построить и на конечных последовательностях (а не только бесконечных)Конечно, с тобой бы гораздо грамотнее поспорили люди, увлекающиеся философией математики, но я готов что-нибудь заботать из этой темы.
Раз уж о математике зашла речь, то давай чуть формальнее.
Да, коряво выразился.
Я имел в виду, что без аксиомы бесконечности невозможно доказать важные теоремы различных разделов математики, например теорему о точной верхней грани.
Я имел в виду, что без аксиомы бесконечности невозможно доказать важные теоремы различных разделов математики, например теорему о точной верхней грани.
думаю, в "сумрачной" математике не будет этих теорем, однако реальность будет описываться возможно даже более полно.
Конечно, с тобой бы гораздо грамотнее поспорили люди, увлекающиеся философией математики, но я готов что-нибудь заботать из этой темы.Я не то, чтобы увлекаюсь, но afaik всякие нестандартные анализы не породили замену классической механики, из задач которой и взялась бесконечность (тут можно ещё апории Зенона вспомнить, которые как раз связаны с основными понятиями механики).
думаю, в "сумрачной" математике не будет этих теорем, однако реальность будет описываться возможно даже более полно.описанием реальности занимается физика.
доказательство в физике - это опыт.
математика не занимается такими вещами. доказательство в математике - это логический вывод из аксиом.
не путайте теплое с мягким
а вот ни фига.
математика дает инструменты для описания реальности. Физика для объяснения происходящего пользуется математикой.
математика дает инструменты для описания реальности. Физика для объяснения происходящего пользуется математикой.
Физика для объяснения происходящего пользуется математикой.вот это правильно.
а математика ничего никому не должна и не дает. у нее берут
она царица всех наук.
ну, я примерно понял твою терминологию. В ней, как мне кажется, пост ДаркГрея будет звучать, как желание построить математику, не используя понятие бесконечности, а затем использовать ее, например, для исследования свойств алгоритмов.
угу
только я думаю, что все велосипеды уже сделаны в этом направлении
бери - катайся
только я думаю, что все велосипеды уже сделаны в этом направлении
бери - катайся
> Я, возможно, чего то не понял, но как соотнести твое утверждение, допустим, с тем, что аксиома бесконечности независима от остальных аксиом теории мн-в Цермело?
и что?
можно провести аналогию с геометриями Евклида и Лобачевского..
была геометрия Евклида - в которой была отдельная аксиома о том, что через две точки можно провести только одну прямую. Потом эту аксиому подвергли сомнению, и допустили, что через две точки можно провести бесконечное число прямых, и получили красивую мощную геометрию Лобачевского.
и что?
можно провести аналогию с геометриями Евклида и Лобачевского..
была геометрия Евклида - в которой была отдельная аксиома о том, что через две точки можно провести только одну прямую. Потом эту аксиому подвергли сомнению, и допустили, что через две точки можно провести бесконечное число прямых, и получили красивую мощную геометрию Лобачевского.
> из задач которой и взялась бесконечность
и где там берется бесконечность?
и где там берется бесконечность?
во всех апориях вроде нужна бесконечность в каком-то виде, чтоб их разрешить
например, про стрелу - в математике нужный формализм появился только в дифференциальном исчислении
например, про стрелу - в математике нужный формализм появился только в дифференциальном исчислении
> Я имел в виду, что без аксиомы бесконечности невозможно доказать важные теоремы различных разделов математики, например теорему о точной верхней грани.
без бесконечно малых или без бесконечно больших?
в чем, по твоему, есть проблема в этом доказательстве?
без бесконечно малых или без бесконечно больших?
в чем, по твоему, есть проблема в этом доказательстве?
>во всех апориях вроде нужна бесконечность в каком-то виде, чтоб их разрешить например, про стрелу
зачем? в чем будет проблема, если бесконечности не будет, а будет дискретность, например, на уровне 10e-9м и 10е-9с?
зачем? в чем будет проблема, если бесконечности не будет, а будет дискретность, например, на уровне 10e-9м и 10е-9с?
зачем? в чем будет проблема, если бесконечности не будет, а будет дискретность, например, на уровне 10e-9м и 10е-9с?
Что такое "дискретность на уровне",
ты хочешь все физ. задачи моделировать материальными точками на сетке с таким шагом?
> в чем будет проблема, если бесконечности не будет, а будет дискретность,
летящая стрела будет покоиться
а ещё более очевидно, что ахиллес не догонит черепаху
летящая стрела будет покоиться
а ещё более очевидно, что ахиллес не догонит черепаху
На изначально пустой ленте
> если мт с четыремя состояниями не остановилась за двадцать тысяч ходов, то она не остановится уже никогда, и это можно доказать сугубо математически, опять же не аппелируя к "бесконечности".
лол.
я знаю алгоритм, который методом деления пополам может остановиться в любой точке конечного куска ленты,
лень его расписывать, но кол-во состояний в нем, вроде, не больше 4.
а ещё более очевидно, что ахиллес не догонит черепахумне неочевидно. Ахиллес не догонит черепаху только если есть бесконечно малые отрезки времени, нет?
ну типа ахиллес в точке N, а черепаха - в точке N+1
1 - квант расстояния
где будет черепаха, когда ахиллес окажется в точке N+1?
1 - квант расстояния
где будет черепаха, когда ахиллес окажется в точке N+1?
если скорость черепахи 1 квант расстояния за квант времени, а ахиллеса — 10 квантов расстояния за квант времени, то ахиллес в точку N+1 не попадет. Он сразу из точки N переместится в точку N+10 и моментом обгона можно считать именно это время.
нифига, в каждой промежуточной точке ахиллес оказаться должен - это экспериментально проверяется: можно где угодно натянуть тонкую верёвку, и он её порвёт
остаётся заключить, что он одновременно в нескольких точках находится - вот и попробуй построй такую механику, пока что afaik ни у кого не получилось
нечто подобное бывает в квантовой механике, но там бесконечность появляется ещё раньше, чем в классической
остаётся заключить, что он одновременно в нескольких точках находится - вот и попробуй построй такую механику, пока что afaik ни у кого не получилось
нечто подобное бывает в квантовой механике, но там бесконечность появляется ещё раньше, чем в классической
нифига, в каждой промежуточной точке ахиллес оказаться должен - это экспериментально проверяется: можно где угодно натянуть тонкую верёвку, и он её порвётделаем вывод, что эксперимент проводится с недостаточно тонкой веревкой.
тот факт, что все верёвки - отстой, ничуть не поможет в построении механики
почему это? мы все также хорошо описываем свойство реальности "если поставить на пути Ахилесса веревку, он ее обязательно порвет".
проблема в том, что ахиллес в модели черепаху не догонит: то он был сзади, и вдруг оказывается спереди
а в реальности - догоняет
значит, модель неадекватна, и для описания реальности (нужно же нам посчитать, когда он таки "догонит" её) придётся использовать что-то ещё, например, всё те же действительные числа
а в реальности - догоняет
значит, модель неадекватна, и для описания реальности (нужно же нам посчитать, когда он таки "догонит" её) придётся использовать что-то ещё, например, всё те же действительные числа
проблема в том, что ахиллес в модели черепаху не догонит: то он был сзади, и вдруг оказывается спередимы уже научились так точно смотреть?
а в реальности - догоняет
вообще, на мой взгляд, все достаточно ясно: без бесконечности обойтись можно, но лучше от этого в ряде приложений не станет. Т.к. бесконечность введена как раз для удобства.
ну а если враг с помощью дифуров изготовит атомную бомбу, а ты - нет, потому что не знаешь дифуров? недолго так ты сможешь обходиться без бесконечности
значит, окажется, что комсомол сам создал себе проблемы и пока их решал, враг сделал атомную бомбу.
однако, может оказаться и по-другому. Пока враг ищет задачи, которые алгоритмически неразрешимы, комсомольцы уже решат эти задачи.
однако, может оказаться и по-другому. Пока враг ищет задачи, которые алгоритмически неразрешимы, комсомольцы уже решат эти задачи.
враг тоже решает алгоритмически неразрешимые задачи, например доказывает теоремы
враг умен
по делу: не вижу цели спора. Если у кого-то есть желание строить полностью конечную модель и решать с помощью нее задачи, которые фигово решаются сейчас: вперед. Если кто-то не верит в реальность этого: пофиг, задачи, которые сейчас не решаются, такими и останутся.
по делу: не вижу цели спора. Если у кого-то есть желание строить полностью конечную модель и решать с помощью нее задачи, которые фигово решаются сейчас: вперед. Если кто-то не верит в реальность этого: пофиг, задачи, которые сейчас не решаются, такими и останутся.
> нифига, в каждой промежуточной точке ахиллес оказаться должен - это экспериментально проверяется: можно где угодно натянуть тонкую верёвку, и он её порвёт
месье ни разу не пробовал разрабатывать программную дискретную модель физ. мира?
стандартное решение - положение элемента в движении описывается вектором (а не точкой если векторы пересекается, то считается, что конфликт, и обсчитывается или затор, или отскок.
при мелкой дискретности - сетка значительно меньше, чем скорости за квант времени - никаких заметных проблем у модели нет.
> нифига, в каждой промежуточной точке ахиллес оказаться должен - это экспериментально проверяется: можно где угодно натянуть тонкую верёвку, и он её порвёт
ты можешь сделать веревку толщиной 10e-10? а я именно такой порядок дискретности я приводил
ps
10e-10 - это порядок размеров атомов
месье ни разу не пробовал разрабатывать программную дискретную модель физ. мира?
стандартное решение - положение элемента в движении описывается вектором (а не точкой если векторы пересекается, то считается, что конфликт, и обсчитывается или затор, или отскок.
при мелкой дискретности - сетка значительно меньше, чем скорости за квант времени - никаких заметных проблем у модели нет.
> нифига, в каждой промежуточной точке ахиллес оказаться должен - это экспериментально проверяется: можно где угодно натянуть тонкую верёвку, и он её порвёт
ты можешь сделать веревку толщиной 10e-10? а я именно такой порядок дискретности я приводил
ps
10e-10 - это порядок размеров атомов
> положение элемента в движении описывается вектором (а не точкой)
вот давай теперь механику без материальных точек выведи
и откажись от экспоненты в обозначаниях, так как её свойства подразумевают наличие бесконечно малых
вот давай теперь механику без материальных точек выведи
и откажись от экспоненты в обозначаниях, так как её свойства подразумевают наличие бесконечно малых
вспомнил кстати основные требования к дискретной физ. модели:
дискретность позиции должна быть как минимум на порядок меньше, чем мин. размеры элемента
макс. скорость за квант времени должна быть меньше, чем мин. размеры элементов
при таких ограничениях модель нормально расчитывается в терминах материальных дискретных точек.
> вот давай теперь механику без материальных точек выведи
и в чем проблема? счетная механика уж точно без проблем вводится, с аналитической, конечно, больше проблем будет, т.к. дискретная математика до сих пор очень слабая.
> и откажись от экспоненты в обозначаниях, так как её свойства подразумевают наличие бесконечно малых
способ записи ни на что не влияет, а то ты сейчас скатишься до того, что в десятичной системе счисления писать нельзя, потому что в мире никакой десятичной системы нет.
дискретность позиции должна быть как минимум на порядок меньше, чем мин. размеры элемента
макс. скорость за квант времени должна быть меньше, чем мин. размеры элементов
при таких ограничениях модель нормально расчитывается в терминах материальных дискретных точек.
> вот давай теперь механику без материальных точек выведи
и в чем проблема? счетная механика уж точно без проблем вводится, с аналитической, конечно, больше проблем будет, т.к. дискретная математика до сих пор очень слабая.
> и откажись от экспоненты в обозначаниях, так как её свойства подразумевают наличие бесконечно малых
способ записи ни на что не влияет, а то ты сейчас скатишься до того, что в десятичной системе счисления писать нельзя, потому что в мире никакой десятичной системы нет.
вспомнил кстати основные требования к дискретной физ. модели:причём строго получить это позволяет наука, известная как "выч. методы", при помощи аналитических методов, в которых повсюду актуальная бесконечность
дискретность позиции должна быть как минимум на порядок меньше, чем мин. размеры элемента
макс. скорость за квант времени должна быть меньше, чем мин. размеры элементов
и в чем проблема? счетная механика уж точно без проблем вводится, с аналитической, конечно, больше проблем будет, т.к. дискретная математика до сих пор очень слабая.я не знаю, в чём проблема, но, по моим данным, это ни у кого не получилось
способ записи ни на что не влияет, а то ты сейчас скатишься до того, что в десятичной системе счисления писать нельзя, потому что в мире никакой десятичной системы нетспособ записи в основаниях математики влияет на все дальнейшие построения
> по делу: не вижу цели спора.
Кратко: в силу некоторого знакомства с историей вопроса, хоть и неглубокого, считаю заявления типа "разработать математические основы механики без актуальной бесконечности - как два пальца обоссать", мягко говоря, необоснованными и преждевременными.
Кратко: в силу некоторого знакомства с историей вопроса, хоть и неглубокого, считаю заявления типа "разработать математические основы механики без актуальной бесконечности - как два пальца обоссать", мягко говоря, необоснованными и преждевременными.
По моим впечатлениям, про основы механики — ты прав. Т.е. без бесконечности обойтись можно, но крайне геморно.
Про теорию алгоритмов и прочую дискретчину, там есть ощущение, что бесконечность можно выкинуть сильно более безболезненно. Сегодня вечером посоветуюсь по этому вопросу у большого специалиста в этой области, возможно он меня переубедит.
Про теорию алгоритмов и прочую дискретчину, там есть ощущение, что бесконечность можно выкинуть сильно более безболезненно. Сегодня вечером посоветуюсь по этому вопросу у большого специалиста в этой области, возможно он меня переубедит.
зачем? в чем будет проблема, если бесконечности не будет, а будет дискретность, например, на уровне 10e-9м и 10е-9с?Был же, был длинный тред про существование натуральных чисел в природе и всё такое, где этот вопрос поднимался.
Да, ты можешь построить сеточную физику с шагом h-с-чертой или всю математику считать в кольце вычетов по модулю 10^10^10. Но прямо сразу, как только ты это попытаешься сделать, у тебя (или у любого разумного человека) возникнет вопрос: а что изменится, если мы шаг уменьшим вдвое или вместо 10^10^10 возьмём 10^10^10^10? Причём есть неслабая вероятность, что этот вопрос неожиданно быстро приобретёт практический смысл, особенно в случае математики, о чём я скажу чуть ниже. Так вот, отвечая на такие вопросы ты немедленно получаешь бесконечность, причём эта бесконечность оказывается гораздо более изящной, чем прямой ответ: легче описать изменения при уменьшении шага сетки в два раза, чем описывать изменения при уменьшении шага сетки конкретно с h до h/2, если ты понимаешь, о чём я. Можно даже утверждать, что такая неявная бесконечность появляется в тот самый момент, когда ты описываешь первую абстрактную функцию (то есть не табличную, а со свободной переменной вроде "a = b + 1", а такой способ описания эффективен и позволяет делать разные штуки.
Теперь возвращаюсь к большим числам и их практическому смыслу. Древние люди описывали числа в base-0 системе счисления, то есть 1=1, 1111=4, 11111111=8 etc. Число 10^10 они уже эффективно описать не могли. Потом были разные хитрые трюки наподобие римских чисел, где вводилось некоторое конечное количество predefined констант, типа V = IIIII, X = VV, L=XXXXX и т.д., которые ещё и комбинировались хитроумно. Потом появилась позиционная система счисления, например, десятичная, которая сделала возможным запись числа 10^10 непосредственно, как 10000000000, но 10^10^10 записать всё ещё было нельзя. Потом наконец появилась Свободная Переменная и формулы, которые позволили записать, например, 10^10^10 именно так, как я его записал. Потом, уже сравнительно недавно, люди научились применять формулы к формулам, в результате появились штуки вроде двойной стрелки Дийкстры (если я ничего не путаю которая в записи 10^^10 означает десятикратное возведение в степень (если я опять же ничего не путаю). В принципе, Busy Beaver и есть конечное звено этой цепи, поскольку на самом-то деле задачу можно сформулировать так: "какое максимальное число можно записать в терминах МТ с N состояниями?"
Я это всё к тому, что алгоритмы, как текущая высшая ступень человеческого знания о числах, очень быстро делают outdated и бессмысленным любое ограничение сверху на область целых чисел, потому что предоставляют возможность работать с очень большими числами, настолько большими, что их даже сверху оценить не представляется возможным. То есть если бы мы спустились на уровень первобытных людей, то можно было бы ограничить все числа, скажем, сотней и жить спокойно, но на нашем уровне уже нельзя.
ты мне о теории чисел, а я тебе о практике...
да, в теории очень удобно работать с бесконечностью, но к практике это имеет слабое отношение.
т.к. на практике у нас всегда есть ограничение в виде: времени, расстояния, памяти, кол-ва атомов во вселенной, размеров атома и т.д.
особенно - это касается задач, где числа появляются косвенно, например в алгоритмах.
причем есть следующая особенность: что если с числами удобнее работать с бесконечными, то с алгоритмами как раз удобнее работать с конечными, т.к. у конечного алгоритма есть хорошее свойство - его всегда можно "решить" полным перебором.
да, в теории очень удобно работать с бесконечностью, но к практике это имеет слабое отношение.
т.к. на практике у нас всегда есть ограничение в виде: времени, расстояния, памяти, кол-ва атомов во вселенной, размеров атома и т.д.
особенно - это касается задач, где числа появляются косвенно, например в алгоритмах.
причем есть следующая особенность: что если с числами удобнее работать с бесконечными, то с алгоритмами как раз удобнее работать с конечными, т.к. у конечного алгоритма есть хорошее свойство - его всегда можно "решить" полным перебором.
> т.к. у конечного алгоритма есть хорошее свойство - его всегда можно "решить" полным перебором
не всегда, а только в теории
на практике как раз обычно нельзя
не всегда, а только в теории
на практике как раз обычно нельзя
Вот полет в космос --- практическая задача?
Решение этой задачи невозможно, если не уметь решать хотя бы такое уравнение:
r'' = -k/r
Ты сейчас скажешь "численное решение с мелкой сеткой" ?
Ну хорошо, а как тогда насчет уравнения Хопфа (используется в гидродинамике и еще много где):
du/dt + d/dx(u^2/2) = 0.
Для такого уравнения существует оптимальный шаг, при котором оно будет иметь решении наиболее близкое к точному. При неограниченном тупом уменьшении шага численная схема как правило разваливается. Так вот, чтобы найти такой шаг используется "непрерывная математика". Кроме того, точное решение этого уравнение в твоей модели очевидно невозможно, так как понятие производная ты даже не определишь. Замечу, что это только один из огромного количества подобных примеров.
PS. И ты мне не ответил на вопрос о формализации используемого тобой понятия.
Решение этой задачи невозможно, если не уметь решать хотя бы такое уравнение:
r'' = -k/r
Ты сейчас скажешь "численное решение с мелкой сеткой" ?
Ну хорошо, а как тогда насчет уравнения Хопфа (используется в гидродинамике и еще много где):
du/dt + d/dx(u^2/2) = 0.
Для такого уравнения существует оптимальный шаг, при котором оно будет иметь решении наиболее близкое к точному. При неограниченном тупом уменьшении шага численная схема как правило разваливается. Так вот, чтобы найти такой шаг используется "непрерывная математика". Кроме того, точное решение этого уравнение в твоей модели очевидно невозможно, так как понятие производная ты даже не определишь. Замечу, что это только один из огромного количества подобных примеров.
PS. И ты мне не ответил на вопрос о формализации используемого тобой понятия.
т.к. на практике у нас всегда есть ограничение в виде: времени, расстояния, памяти, кол-ва атомов во вселенной, размеров атома и т.д.Вот я тебе и пытаюсь объяснить, что если ты числа записываешь в base-0 системе счисления, то количество атомов во вселенной является более чем разумным ограничением, а если с использованием стрелки Дийкстры, то нифига подобного. И что самое для тебя ужасное, с такими чудовищными числами (большими, чем число атомов во вселенной) вполне можно работать и получать интересные результаты именно про эту вселенную, с очень маленьким количеством атомов.
каким образом из наличия стрелки Дийкстры ты делаешь вывод, что у тебя появляется бесконечность?
Надо полагать, так: точная верхняя грань объединения всех множеств вида (<10^)^n)10) = \inf, и бесконечность тут потенциальная.
Видишь ли ты разницу между бесконечностями, как вижу её я?
Одно дело — когда некто постулирует, что для любого _конечного_ натурального числа N существует натуральное число N+1. Другое — когда в комплексном анализе, например, рассматриваются разнообразные преобразования, в ходе которых появляется некая "бесконечно удалённая точка", которая в результате преобразования превращается в обычную точку, и наоборот.
Разница очень subtle для не-математика, но крайне существенная. От эпсилон-дельта формализма до *R (hyperreal numbers, см. Википедию в который "бесконечно малые" являются настоящими числами, нужно сделать довольно большой (и рискованный, на мой взгляд) шаг.
Так вот, я говорю именно о потенциальной бесконечности, которая мешает тебе сказать "а теперь мы будем производить все действия в кольце вычетов по модулю 10^10^10, потому что во вселенной меньше атомов" — мешает тем, что Дийкстра изобретает свою стрелку, а когда ты заменяешь 10^10^10 на 10^^(количество атомов во вселенной то тебе демонстрируют функцию Акерманна (P(m, n) = P(m-1, P(m, n-1 базис очевиден которая, если её привести к одноаргументному виду (P'(n) = P(n, n растёт ещё быстрее. И единственным способом выхода из порочного круга, на мой взгляд, является постулирование модуля в виде той самой BusyBeaver(N = количество_атомов_во_вселенной но к счастью ты её и для N = 5 посчитать не можешь, не говоря уж о количестве атомов во вселенной. И приходится жить с потенциальной бесконечностью.
Пока Контра не увидел этот тред, я вообще философскую вещь скажу: тут получается вот какая штука, если ты хочешь как-то специфицировать Самое Большое Натуральное Число (в том смысле, что бОльшие числа никого не интересуют то тебе нужно придумать способ как-то это Самое Большое Число записать. Но ведь наверняка кто-то сумеет к этой записи прибавить единичку и получить Число Ещё Больше, а раз его, это Число Ещё Больше, удалось записать, то оно непременно вызовет интерес, типа простое ли оно, например. Получается, что ты не можешь записать Самое Большое Число (из интересных ну и все разговоры на эту тему оказываются ещё более абстрактными, чем математика с бесконечностями.
Одно дело — когда некто постулирует, что для любого _конечного_ натурального числа N существует натуральное число N+1. Другое — когда в комплексном анализе, например, рассматриваются разнообразные преобразования, в ходе которых появляется некая "бесконечно удалённая точка", которая в результате преобразования превращается в обычную точку, и наоборот.
Разница очень subtle для не-математика, но крайне существенная. От эпсилон-дельта формализма до *R (hyperreal numbers, см. Википедию в который "бесконечно малые" являются настоящими числами, нужно сделать довольно большой (и рискованный, на мой взгляд) шаг.
Так вот, я говорю именно о потенциальной бесконечности, которая мешает тебе сказать "а теперь мы будем производить все действия в кольце вычетов по модулю 10^10^10, потому что во вселенной меньше атомов" — мешает тем, что Дийкстра изобретает свою стрелку, а когда ты заменяешь 10^10^10 на 10^^(количество атомов во вселенной то тебе демонстрируют функцию Акерманна (P(m, n) = P(m-1, P(m, n-1 базис очевиден которая, если её привести к одноаргументному виду (P'(n) = P(n, n растёт ещё быстрее. И единственным способом выхода из порочного круга, на мой взгляд, является постулирование модуля в виде той самой BusyBeaver(N = количество_атомов_во_вселенной но к счастью ты её и для N = 5 посчитать не можешь, не говоря уж о количестве атомов во вселенной. И приходится жить с потенциальной бесконечностью.
Пока Контра не увидел этот тред, я вообще философскую вещь скажу: тут получается вот какая штука, если ты хочешь как-то специфицировать Самое Большое Натуральное Число (в том смысле, что бОльшие числа никого не интересуют то тебе нужно придумать способ как-то это Самое Большое Число записать. Но ведь наверняка кто-то сумеет к этой записи прибавить единичку и получить Число Ещё Больше, а раз его, это Число Ещё Больше, удалось записать, то оно непременно вызовет интерес, типа простое ли оно, например. Получается, что ты не можешь записать Самое Большое Число (из интересных ну и все разговоры на эту тему оказываются ещё более абстрактными, чем математика с бесконечностями.
А надо запретить записывать это число и вообще упоминать его, и проблема снята.
Вернее, запрещать нельзя, у нас же не кровавый тоталитаризм, но можно демократическим путём не брать мечтателей на интеллектуальную работу ввиду непригодности. Пожарят картошку в макдональдсе, сами всё поймут.
Вернее, запрещать нельзя, у нас же не кровавый тоталитаризм, но можно демократическим путём не брать мечтателей на интеллектуальную работу ввиду непригодности. Пожарят картошку в макдональдсе, сами всё поймут.
> Видишь ли ты разницу между бесконечностями, как вижу её я?
с точки зрения алгоритмов важны другие бесконечности....
т.е. в первую очередь важно, есть у нас верхняя конечная оценка размерности алгоритма или нет?
если есть - значит алгоритм конечен, если нет - значит алгоритм бесконечен.
машина Тьюринга по этому определению бесконечна.
но все практические задачи - конечны.
с точки зрения алгоритмов важны другие бесконечности....
т.е. в первую очередь важно, есть у нас верхняя конечная оценка размерности алгоритма или нет?
если есть - значит алгоритм конечен, если нет - значит алгоритм бесконечен.
машина Тьюринга по этому определению бесконечна.
но все практические задачи - конечны.
но все практические задачи - конечны.Да?
конечно, потому что до результата бесконечной задачи человек уж заведомо не доживет.
конечно, потому что до результата бесконечной задачи человек уж заведомо не доживет.Разве из этого следует конечность всех практических задач? Мы ведь можем запустить некоторую, вообще говоря, бесконечную задачу, но при этом нас сам ход решения будет интересовать больше, чем результат.
> Мы ведь можем запустить некоторую, вообще говоря, бесконечную задачу, но при этом нас сам ход решения будет интересовать больше, чем результат
из примеров, только разве что - смысл жизни.
> Мы ведь можем запустить некоторую, вообще говоря, бесконечную задачу, но при этом нас сам ход решения будет интересовать больше, чем результат
откуда в практической задачи берется бесконечность?
все входные параметры, на практике, у нас конечны:
1. время - конечно
2. пространство - конечно
3. материалы - конечны
и т.д.
из примеров, только разве что - смысл жизни.
> Мы ведь можем запустить некоторую, вообще говоря, бесконечную задачу, но при этом нас сам ход решения будет интересовать больше, чем результат
откуда в практической задачи берется бесконечность?
все входные параметры, на практике, у нас конечны:
1. время - конечно
2. пространство - конечно
3. материалы - конечны
и т.д.
дело в том, что многие практические задачи, связанные с обработкой данных нельзя решать исходя из конечности приведенных тобой параметров.
Объемы данных постоянно растут. Если считать, что алгоритмы конечны и разрабатываются именно с такой позиции, то в итоге придется переписывать алгоритм, когда понадобится расширение, а это не круто.
Например (не про то что только что написал, но всеже когда-то люди думали что достаточно двух цифр для хранения информации о годе. Настал момент и все критически важные алгоритмы связанные с переходом времени пришлось переписывать.
Рассмотрение конечных алгоритмов (например МТ с конечной лентой) сводится к конечным автоматам, которые не так интересны, как алгоритмы и менее универсальны. Я так и не понял из твоих постов, чем конечные автоматы (КА) лучше алгоритмов. (даже учитывая то, что на конечных данных любой алгоритм реализуется при помощи КА)
Объемы данных постоянно растут. Если считать, что алгоритмы конечны и разрабатываются именно с такой позиции, то в итоге придется переписывать алгоритм, когда понадобится расширение, а это не круто.
Например (не про то что только что написал, но всеже
когда-то люди думали что достаточно двух цифр для хранения информации о годе. Настал момент и все критически важные алгоритмы связанные с переходом времени пришлось переписывать.Рассмотрение конечных алгоритмов (например МТ с конечной лентой) сводится к конечным автоматам, которые не так интересны, как алгоритмы и менее универсальны. Я так и не понял из твоих постов, чем конечные автоматы (КА) лучше алгоритмов. (даже учитывая то, что на конечных данных любой алгоритм реализуется при помощи КА)
> скорее всего влез в эту тему сам того не понимая, и продолжает непонимать, почему я об этом начал писать.Либо я что-то не догнал из фразы, либо это просто брэхня. Классический пример задачи (дискретной которую невозможно решить, не используя понятий типа "существование бесконечной последовательности, обладающей свойством...":
О, Великий Гуру развей, пожалуйста, мое невежество, и покажи на пальцах что именно я не понимаю.
ps
я смотрю дальше, чем твои отсылки к началам, и утверждаю, что все тоже самое дерево математики можно построить и на конечных последовательностях (а не только бесконечных)
Даны натуральные числа N и K. N записывается в виде суммы разрядных слагаемых с основанием K (пример: K=3, N=25=2*3^2+2*3^1+1*3^0 затем все показатели записываются в таком же виде и т.д. Над числами N и K последовательно проводятся 2 операции (N,K - типа переменные):
1) K увеличивается на 1, и в представлении N с основанием K везде K заменяется на K+1;
2) N уменьшается на 1.
Доказать, что при любых начальных K>=2 и N последовательность сойдется к 0.
Пример: N=11, K=2
Начало последовательности: 1*2^(1*2^1+1)+1*2^1+1= 11 -> 1*3^(1*3^1+1)+1*3^1+1 = 85 -> 1*3^(1*3^1+1)+1*3^1 = 84 -> 1*4^(1*4^1+1)+1*4^1= 1028 -> ...
Задачу можно сформулировать в терминах конечных последовательностей, но решить - нельзя.
Респект!
Я совсем забыл про этот пример.
Я совсем забыл про этот пример.
Практическое применение бесконечности.
На практике бесконечность может использоваться для доказательства свойств алгоритмов (в том числе конечных). К примеру, есть некий алгоритм (в виде конечного автомата обрабатывающий входные данные размером до 10^12 (вполне реально). Мы хотим узнать, правильно он это делает или нет. Может быть, что "чисто конечное" доказательство занимает объем что-то типа 2^(10^12) символов, а доказательство с использованием каких-нибудь "бесконечных" теорем в виде конечных частных случаев занимает 10^20 символов (что уже реально проверить).
P.S. Ещё говорят, что ответить на вопрос P?=NP без привлечения "чисто бесконечной математики" скорее всего нельзя. Поговаривают даже, что это утверждение независимо с ZFC.
На практике бесконечность может использоваться для доказательства свойств алгоритмов (в том числе конечных). К примеру, есть некий алгоритм (в виде конечного автомата обрабатывающий входные данные размером до 10^12 (вполне реально). Мы хотим узнать, правильно он это делает или нет. Может быть, что "чисто конечное" доказательство занимает объем что-то типа 2^(10^12) символов, а доказательство с использованием каких-нибудь "бесконечных" теорем в виде конечных частных случаев занимает 10^20 символов (что уже реально проверить).
P.S. Ещё говорят, что ответить на вопрос P?=NP без привлечения "чисто бесконечной математики" скорее всего нельзя. Поговаривают даже, что это утверждение независимо с ZFC.
щас скажет, что некорректно формулировать задачу "для любых N, K ...", так как имеем бесконечный перебор.
Поговаривают даже, что это утверждение независимо с ZFCА вот это жесть, но такое хрен вот так докажешь, надо строить еще что-то более общее, чем ZFC
А вообще есть такие системы, кстати ?
Задачу можно сформулировать в терминах конечных последовательностей, но решить - нельзя.ответ - элементарный.
для конечных последовательностей - утверждение
Доказать, что при любых начальных K>=2 и N последовательность сойдется к 0неверно.
контрпример
конечная последовательно длиной 30.
N=11, K=2
А вообще есть такие системы, кстати ?Вообще, есть. Например, ZFC + непротиворечивость ZFC или ZFC + корректность ZFC относительно множества натуральных чисел. Ещё иногда добавляют к ZFC существование очень больших кардиналов (типа сверхдох*я
) или универсума ZFC. Правда чем шире аксиоматика, тем меньше верится в её непротиворечивость. Знаю, есть учОные, активно с пеной у рта доказывающие противоречивость формальной арифметики Пеано, я уж не говорю о расширениях ZFC.контрпримерДык она всегда конечная.
конечная последовательно длиной 30. N=11, K=2
Но доказать это для любых N и K без привлечения "бесконечностей" не получится.
Ну непротиворечивость это хрен с ней, но можно вполне доказывать сводимость к PRA подсистем (а значит, в частности. - конкретных теорем) в арифметике Пеано или в Z2.
а может PRA тоже противоречива?
гы-гы-гы
Гильберт все ж таки авторитетный товарищ, будем ему верить
Гильберт все ж таки авторитетный товарищ, будем ему верить
> Дык она всегда конечная.
ты не понял.
в определение задачи, опять же используется, что числовая последовательность бесконечная.
соответственно я утверждаю, что если брать числовую последовательность конечную (например, длиной 30 то утверждение задачи сразу становится неверной.
ты не понял.
в определение задачи, опять же используется, что числовая последовательность бесконечная.
соответственно я утверждаю, что если брать числовую последовательность конечную (например, длиной 30 то утверждение задачи сразу становится неверной.
соответственно я утверждаю, что если брать числовую последовательность конечную (например, длиной 30 то утверждение задачи сразу становится неверной.А какой смысл другую задачу рассматривать?
Задача была: есть бесконечная последовательность; доказать, что в ней есть 0.
Или в конечном виде: существует натуральное m такое, что если построить конечную последовательность длины m, то у неё будет на конце 0.
>Задача была: есть бесконечная последовательность
точно. теорема гудстейна - задача о бесконечных последовательностях, и то, что для её доказательства не хватает обычной индукции, а нужна трансфинитная - расплата за бесконечность в условии.
точно. теорема гудстейна - задача о бесконечных последовательностях, и то, что для её доказательства не хватает обычной индукции, а нужна трансфинитная - расплата за бесконечность в условии.
> А какой смысл другую задачу рассматривать?
ты о чем, вообще, хочешь поговорить?
утверждалось, что реальный мир конечен, соответственно на практических задачах удобнее работать с "конечностями", а не c бесконечностями.
далее приходишь ты, и говоришь, но ведь если мы возьмем задачу в которой в условиях присутствует бесконечная числовая прямая, то мы ее не сможем решить с помощью "конечной" математики...
внимание, вопрос: какое отношение твой пример имеет к моему утверждению?
могу спросить более медленно:
какое отношение имеет задача, которая в условии требует наличие бесконечной прямой, к моему утверждению, что на конечных задачах нужна, в первую очередь, "конечная" математика?
ты о чем, вообще, хочешь поговорить?
утверждалось, что реальный мир конечен, соответственно на практических задачах удобнее работать с "конечностями", а не c бесконечностями.
далее приходишь ты, и говоришь, но ведь если мы возьмем задачу в которой в условиях присутствует бесконечная числовая прямая, то мы ее не сможем решить с помощью "конечной" математики...
внимание, вопрос: какое отношение твой пример имеет к моему утверждению?
могу спросить более медленно:
какое отношение имеет задача, которая в условии требует наличие бесконечной прямой, к моему утверждению, что на конечных задачах нужна, в первую очередь, "конечная" математика?
бля
ну сколько можно?
реальный мир, может, и конечен, но границу заранее не выставишь
например, реальная программа, работающая на реальном компьютере, занимающем лишь ничтожную долю всего вещества вселенной, полностью протестировать за время жизни этой вселенной нереально
потому что экспонента
а задача тестирования программ - вполне практична и актуальна
ты хуже контровского студента, тому всего три раза надо повторять
ну сколько можно?
реальный мир, может, и конечен, но границу заранее не выставишь
например, реальная программа, работающая на реальном компьютере, занимающем лишь ничтожную долю всего вещества вселенной, полностью протестировать за время жизни этой вселенной нереально
потому что экспонента
а задача тестирования программ - вполне практична и актуальна
ты хуже контровского студента, тому всего три раза надо повторять
> например, реальная программа, работающая на реальном компьютере, занимающем лишь ничтожную долю всего вещества вселенной, полностью протестировать за время жизни этой вселенной нереально
а бесконечность где?
а бесконечность где?
какое отношение имеет задача, которая в условии требует наличие бесконечной прямой, к моему утверждению, что на конечных задачах нужна, в первую очередь, "конечная" математика?Короче, я наверно неправильно понял твою фразу
и утверждаю, что все тоже самое дерево математики можно построить и на конечных последовательностях (а не только бесконечных)Но польза от бесконечности всё-таки есть: с помощью бесконечной математики бывает возможно существенно уменьшать размер доказательств свойств конечных объектов (типа полином вместо экспоненты где-нибудь) и, следовательно, возможно проще проверять свойства конечных объектов.
точно. теорема гудстейна - задача о бесконечных последовательностях, и то, что для её доказательства не хватает обычной индукции, а нужна трансфинитная - расплата за бесконечность в условии.НЕТ!
Эту задачу можно переформулировать в конечном виде (доказать, что для любых N, K существует m такое, что конечная последовательность из m членов, построенная по правилам, заканчивается нулём).
Кроме того, можно взять аналогичную задачу (тоже о якобы бесконечных последовательностях):
Дано натуральное N. За 1 шаг оно уменьшается на 1. Доказать, что рано или поздно появится 0.
Вот эта задача очень хорошо решается конечными методами.
Эту задачу можно переформулировать в конечном виде (доказать, что для любых N, K существует m такое, что конечная последовательность из m членов, построенная по правилам, заканчивается нулём).
это не в конечном виде, это ты просто слово "бесконечный" в формулировке "спрятал".
в конечном виде было бы так: конечная последовательность из не более (подставить _число_ по вкусу) членов.
ну если за время жизи вселенной что-то нельзя сделать, то на практике получается бесконечность, так?
уже четвёртый раз, контра отдыхает
уже четвёртый раз, контра отдыхает
P.S. Ещё говорят, что ответить на вопрос P?=NP без привлечения "чисто бесконечной математики" скорее всего нельзя. Поговаривают даже, что это утверждение независимо с ZFC.Вот тут: http://www.scottaaronson.com/papers/npcomplete.pdf умный дядька Scott Aaronson рассуждает на тему того, что P!=NP является чем-то вроде физического закона. Типа, что если бы P было равно NP, то можно было бы делать разные штуки, которые, с точки зрения физики нашей вселенной, являются слегка невозможными.
С математической точки зрения, кстати, P=NP приводит к тому, что можно достаточно быстро получить ответ на вопрос "есть ли у данной теоремы доказательство короче N символов", а это как-то непривычно очень.
это не в конечном виде, это ты просто слово "бесконечный" в формулировке "спрятал".в конечном виде было бы так: конечная последовательность из не более (подставить _число_ по вкусу) членов.В чём-то ты прав, конечно.
Я имел в виду, что в формулировке утверждения используются только конечные объекты (неограниченного размера) и кванторы по ним (хотя сами кванторы бесконечные).
> ну если за время жизи вселенной что-то нельзя сделать, то на практике получается бесконечность, так?
нет, конечно.
простой пример: если решение бесконечной задачи улучшить даже экспонециально, то лучше от этого не станет.
если же конечную задачу улучшить во столько же, то есть большая вероятность, что это уже можно будет применить на практике.
возьмем те же сегодняшние шифры: их взлом является конечной задачей, соответственно когда в современных шифрах или в генераторах ключей находятся слабости, которые в разы, а иногда и экспонециально упрощают взлом, то взлом сразу становится реальным.
нет, конечно.
простой пример: если решение бесконечной задачи улучшить даже экспонециально, то лучше от этого не станет.
если же конечную задачу улучшить во столько же, то есть большая вероятность, что это уже можно будет применить на практике.
возьмем те же сегодняшние шифры: их взлом является конечной задачей, соответственно когда в современных шифрах или в генераторах ключей находятся слабости, которые в разы, а иногда и экспонециально упрощают взлом, то взлом сразу становится реальным.
ну так "конечная" математика отлично доказывает, что некоторые конечные задачи, типа тестирования конечных автоматов (то есть практических алгоритмов) не могут быть ускорены
так что вовсе не бесконечность мешает анализу алгоритмов
так что вовсе не бесконечность мешает анализу алгоритмов
> ну так "конечная" математика отлично доказывает, что некоторые конечные задачи, типа тестирования конечных автоматов (то есть практических алгоритмов) не могут быть ускорены
во-первых, неочевидно, т.е. совсем неочевидно, что тестирование всех(большей части) конечных автоматов не может быть ускорено.
во-вторых, кроме полного тестирования, есть еще тестирование с заданной точностью - которое тем более может быть ускорено, и успешно ускоряется.
во-первых, неочевидно, т.е. совсем неочевидно, что тестирование всех(большей части) конечных автоматов не может быть ускорено.
во-вторых, кроме полного тестирования, есть еще тестирование с заданной точностью - которое тем более может быть ускорено, и успешно ускоряется.
> так что вовсе не бесконечность мешает анализу алгоритмов
проблема в отсутствии хорошей конечной математики.
проблема в отсутствии хорошей конечной математики.
во-первых, неочевидно, т.е. совсем неочевидно, что тестирование всех(большей части) конечных автоматов не может быть ускорено.Неочевидно. Но очень похоже на правду — по аналогии со сжимаемостью строчек (ака Колмогоровская сложность). А что ты вообще под тестированием имеешь в виду?
А что ты вообще под тестированием имеешь в виду?проверка какой результат выдают все пути в программе.
Но очень похоже на правду — по аналогии со сжимаемостью строчек (ака Колмогоровская сложность).вообще-то для упрощения задачи тестирования проходит даже такая простая эвристика, как метод разделения на части
кол-во путей в полной программе - 2^N, где N - кол-во условных переходов
если программу разбить на две части и зафиксировать что должна делать каждая отдельная часть, то сложность задачи тестирования будет всего лишь 2^(N/2) + 2^(N/2)=2^(1+n/2)
Представляю, какая должна быть конечная математика.
Теорема 1 (Иванов, 2017). Если в матрице n * n+1 (n<=1023) из нулей и единиц в каждом столбце как минимум одна единица, то существует строка, в которой как минимум две единицы.
Конечные автоматы для проверки условий теоремы для данной матрицы прилагаются (на вход подается матрица 1023*1024 и 10 бит двоичной записи n).
Доказательство. ... (30 MB).
Теорема 2 (Петров, 2023). Если в матрице n * n+1 (n<=8191) из нулей и единиц в каждом столбце как минимум одна единица, то существует строка, в которой как минимум две единицы.
Конечные автоматы для проверки условий теоремы для данной матрицы прилагаются (на вход подается матрица 8191*8192 и 13 бит двоичной записи n).
Доказательство. ... (70 MB).
и т.д.
Теорема 1 (Иванов, 2017). Если в матрице n * n+1 (n<=1023) из нулей и единиц в каждом столбце как минимум одна единица, то существует строка, в которой как минимум две единицы.
Конечные автоматы для проверки условий теоремы для данной матрицы прилагаются (на вход подается матрица 1023*1024 и 10 бит двоичной записи n).
Доказательство. ... (30 MB).
Теорема 2 (Петров, 2023). Если в матрице n * n+1 (n<=8191) из нулей и единиц в каждом столбце как минимум одна единица, то существует строка, в которой как минимум две единицы.
Конечные автоматы для проверки условий теоремы для данной матрицы прилагаются (на вход подается матрица 8191*8192 и 13 бит двоичной записи n).
Доказательство. ... (70 MB).
и т.д.
> проблема в отсутствии хорошей конечной математики
нормальная математика, просто ты не в курсе
нормальная математика, просто ты не в курсе
кол-во путей в полной программе - 2^N, где N - кол-во условных переходовбольше
на самом деле в короткой программе их может быть "дохуя" (так как бесконечности у нас не бывает)
> Представляю, какая должна быть конечная математика.
Не, можно не так. Можно страховать от неверных теорем, которые будут доказаны с заранее заданной точностью Страховые компании, чтобы оптимизировать прибыль, будут тайно от общества использовать запрещённую бесконечную математику.
Не, можно не так. Можно страховать от неверных теорем, которые будут доказаны с заранее заданной точностью
Страховые компании, чтобы оптимизировать прибыль, будут тайно от общества использовать запрещённую бесконечную математику.
вообще-то для упрощения задачи тестирования проходит даже такая простая эвристика, как метод разделения на части
кол-во путей в полной программе - 2^N, где N - кол-во условных переходов
Количество атомов во вселенной оценивается скромным числом 10^67. (где-то встречал 10^77)
То есть для того чтобы перебрать все пути программы с количеством условных переходов порядка нескольких сотен (а таковыми являются сейчас достаточно большое количество программ) не хватит никаких существующих на практике ресурсов.
никакой связи нет между двумя высказываниями (тем более следствия ;
Количество атомов во вселенной оценивается скромным числом 10^67. (где-то встречал 10^77)
То есть для того чтобы перебрать все пути программы с количеством условных переходов порядка нескольких сотен (а таковыми являются сейчас достаточно большое количество программ) не хватит никаких существующих на практике ресурсов.
Чуть более подробно:
Для того чтобы перебрать все пути в программе необходимо по крайней мере различать разные пути. А для этого необходимо хранить о каждом информацию.
Путей может быть 10^100, 10^1000. То есть описать на практике (учитывая развитие технологий в настоящий момент) множество путей в такой программе мы не сможем. Следовательно не сможем и реализовать на практике такой алгоритм.
Для того чтобы перебрать все пути в программе необходимо по крайней мере различать разные пути. А для этого необходимо хранить о каждом информацию.
Путей может быть 10^100, 10^1000. То есть описать на практике (учитывая развитие технологий в настоящий момент) множество путей в такой программе мы не сможем. Следовательно не сможем и реализовать на практике такой алгоритм.
Для того чтобы перебрать все пути в программе необходимо по крайней мере различать разные пути. А для этого необходимо хранить о каждом информацию.вот это не понял. зачем о каждом хранить информацию? еще мы подразумеваем, что для хранения единицы информацию тратится хотя бы один атом нашей вселенной?:)
несложно предложить алгоритм, который на выходе дает слово любой длины. даже длины большей, чем кол-во атомов во вселенной.
вот это не понял. зачем о каждом хранить информацию?Вопросы про то как именно устроен этот алгоритм лучше задавать -у, т.к. ему лучше знать. Я лишь только могу предполагать.
На сколько я понял, он собирается хранить результат тестирования для каждой последовательности. Если есть другие варианты, то прошу предоставить их
.еще мы подразумеваем, что для хранения единицы информацию тратится хотя бы один атом нашей вселенной?:)
Я подразумеваю, что оценивать размеры хранимой информации количеством атомов - это давать сильную фору по отношению к существующим технологиям. Но даже с этой форой описанный алгоритм нельзя реализовать на практике (если я правильно понял этот алгоритм).
Оставить комментарий
Landstreicher
Сегодня у нас неожиданно возникла бурная дискуссия по поводу очевидного на первый взгляд вопроса. А именно, каково строгое математическое определение алгоритма? Поскольку к единому мнению на этот счет мы не пришли, то решил спросить тут.Какие вам известны математически строгие определения алгоритма? Если вам известно несколько, перечислите, пожалуйста, все.
Кроме того, представляет интерес то, как связаны между собой следующие понятия:
1) алгоритм;
2) функция;
3) программа как последовательность букв;
4) программа как процесс в памяти компьютера.
В каких случаях два алгоритма можно считать одинаковыми?