Форум: Проблемы искусственного интеллекта

Регистрация | Вход

Все темы | Новая тема  Стр.5 (6) << < Пред. | След. > >>    Поиск:
Автор	Тема: На: Счетность вещественных чисел
гость 85.202.230.*	На: Счетность вещественных чисел Добавлено: 07 сен 10 18:19 То есть цепочка логических умозаключений описывает порядок действий для решения задачи за конечное время? А постановки задач теперь надо доказывать. Нет, вы явно что то путаете, попробуйте разобраться. [Ответ][Цитата]
Весёлый Роджер Сообщений: 62	На: Счетность вещественных чисел Добавлено: 07 сен 10 18:52 Цитата: Автор: гость 85.202.230.* Самое элементарное - проблема остановки. Заинтересовала эта ботва, однако, заглянул на страничку вики: http://ru.wikipedia.org/wiki/Проблема_останова Прикольно: Цитата: Алан Тьюринг доказал в 1936 году, что общий алгоритм для решения проблемы остановки для любых возможных входных данных не может существовать. Мы можем сказать, что проблема остановки неразрешима на машине Тьюринга. Я конеч, Тьюринга уважаю, глубокоуважуха ему за его труды, но я не согласен, что "проблема остановки" алгоритмически не разрешима. Итак, давайте построим общий алгоритм решения данной проблемы для любых входных данных. Для начала, покритикую набросок доказательства(из вики) о том что данный алгоритм нельзя построить. Цитата: Первое предложения наброска доказательства(из вики): Рассмотрим множество S алгоритмов, которые принимают на вход натуральное число и на выходе тоже выдают натуральное число. Как может алгоритм принять на вход натуральное число? Алгоритм на вход может принять только информацию, а информация выражается в виде конечной строки символов, конечного числа ячеек памяти и т.п. (тут можно говорить по разному, кому как удобнее). Но никак алгоритм не может принять натуральное число. Можно съэмулировать натуральное число введя определенную систему счисления и определив каждую ячейку памяти, какой ячейки какой разряд позиционной записи натурального числа соотвествует, причем что любой алгоритм может рассматривать лишь конечный набор натуральных чисел. В пример калькулятор - 8 разрядов. И алгоритмы сложения(умножения) реализованные аппаратно работают лишь в этом пределе. Натуральное число в своем виде может быть на бумаге, в голове, но никак не в машине. После первой строчки, такого бреда, далее доказательство не читал... Итак пусть задан язык на котором дан алгоритм , который использует конечную память размера бит, в которую изначально помещена некая информация(входные данные). Так как любой алгоритм конечен, то алгоритм возможно представить в виде конечной строки : , где - элементарная команда на языке . Число будем называть длиной алгоритма. Совокупность значений всех ячеек памяти в определенный момент выполнения алгоритма будем называть - состоянием алгоритма. Тогда, по условию задачи, требуется определить достигнет ли алгоритм конца, то есть операции . Теорема: Если при выполнении алгоритма, определенный шаг алгоритма выполнялся дважды при одинаковых состояниях алгоритма, то при заданных входных данных данный алгоритм - не достигнет конца. Доказательство от противного в одну процедуру (предлагается самостоятельно). Теперь построим алгоритм проверки алгоритма на конечность. Для понадобится памяти. Обнулим память. Сформулируем алгоритм преобразовав алгоритм , добавлением после каждой команды процедуру . Получаем ввиде Процедуру определим следующим образом: 1. Обращается в память по старшему адресу , по младшему адресу равному состоянию . Если там "1" - закончить работу, с возвращением того что не конечен. Если там "0" - записать "1", продолжить. Если достиг конца, то алгоритм конечен. В итоге, в максимуме за шагов можно определить является ли конечным. Полученных алгоритм дикий по вычислительной сложности, экспоненциален как по времени, так и по памяти. Но это алгоритм, проверки любого алгоритма на конечность. Где не ясно выразился, спрашивайте. Может еще есть задачки, которые считаются алгоритмически неразрешимыми? [Ответ][Цитата]
VGΨ Сообщений: 666	На: Счетность вещественных чисел Добавлено: 07 сен 10 19:57 Цитата: Автор: Весёлый Роджер Может еще есть задачки, которые считаются алгоритмически неразрешимыми? у меня такой вопрос, о принципах неопределенности вообще. может ли "внутри" алгоритма возникнуть неопределенность/недетерминированость, есть ли у алгоритма "свобода воли"? то что неопределеность может быть задана извне понятно, но если внутри алгоритма все денерминировано, то может ли существовать Демон Лапласа для любого алгоритма? [Ответ][Цитата]
гость 85.202.230.*	На: Счетность вещественных чисел Добавлено: 07 сен 10 20:07 Все, чтобы не травмировать свою психику, я тут больше не буду писать. Читайте книги, ставте опыты. Возможно, скоро и вы станете другом мудрости. [Ответ][Цитата]
VGΨ Сообщений: 666	На: Счетность вещественных чисел Добавлено: 07 сен 10 20:30 Цитата: Автор: гость 85.202.230.* Все, чтобы не травмировать свою психику, я тут больше не буду писать. Читайте книги, ставте опыты. Возможно, скоро и вы станете другом мудрости. ну да здесь писать, надо формулировать мысли ясно, хотя бы говорить к кому обращаетесь, и чем вы недовольны. Совет читать книги, оставвьте для себя, это риторика, а если уж посылаете к литературе, указывайте литературу, желательно до страницы и что отуда надо понять. но похоже просто вы неимеете что сказать? или непонимате а переспросить стесняетесь? Ps. вы много и охотно обясняли НовомуПоиску и ИмеющемуЦель, в ответ на их глупости, а как только вам задали вопрос потруднее, потеряли интерес. Pps. я могу спокойно воспринимать когда кто-то говорит глупости или пытается доказать чего не знает сам, но извените, терпеть не могу разочаровываться в людях, ждешь от человека, что он предмет знает луше тебя и с ним можно поспорить и он тебе обяснит, а в результате получаеш ...поведение [Ответ][Цитата]
daner Сообщений: 4593	На: Счетность вещественных чисел Добавлено: 08 сен 10 4:01 >>> Весёлый Роджер "...дан алгоритм , который использует конечную память..." Вообще-то М.Т. использует бесконечную ленту памяти. [Ответ][Цитата]
NewPoisk Сообщений: 3745	На: Счетность вещественных чисел Добавлено: 08 сен 10 7:55 Цитата: Автор: гость То есть цепочка логических умозаключений описывает порядок действий для решения задачи за конечное время? Да, только "за конечное время" не надо (введение понятия "время" влечет введение в рассмотрение физ. реальности, а "конечное" - соответственно "бесконечное"). Цитата: Автор: гость А постановки задач теперь надо доказывать. Я не понял что вы хотели этим сказать. [Ответ][Цитата]
daner Сообщений: 4593	На: Счетность вещественных чисел Добавлено: 08 сен 10 13:04 Цитата: Автор: гост 88.215Ψ у меня такой вопрос, о принципах неопределенности вообще. может ли "внутри" алгоритма возникнуть неопределенность/недетерминированость, есть ли у алгоритма "свобода воли"? то что неопределеность может быть задана извне понятно, но если внутри алгоритма все денерминировано, то может ли существовать Демон Лапласа для любого алгоритма? на теоретический вопрос -- теоретический ответ. Смотря что вы под алгоритмом подразумеваете. Если вообще любой теоретический алгоритм, то есть алгоритмы для не детерминированных устройств (типа не детерминированных М.Т.), вероятностных и т.д. В них конечно может возникнуть все, что угодно и даже должно возникать по определению некоторых из них. Но что может обычная МТ, то могут и они (только быстрее). А если рассматривать простую МТ (детерминированную) типа нашего с вами компьютера, то конечно никакой неопределенности в них нет. Но извне поступает столько неопределенности, что хватает с лихвой и большинство известных мне ИИ алгоритмов именно с этой неопределенностью пытаются бороться. А "свобода воли" -- это вообще не из этой оперы. [Ответ][Цитата]
гость 85.202.230.*	На: Счетность вещественных чисел Добавлено: 08 сен 10 19:16 гост 88.215Ψ, Я готов с вами обсудить проблему остановки, если вы создадите для этого отдельную тему. Но касательно проблемы, обсуждаемой в этом разделе, я уже написал все выше. [Ответ][Цитата]
Весёлый Роджер Сообщений: 62	На: Счетность вещественных чисел Добавлено: 08 сен 10 20:16 Цитата: Автор: daner Вообще-то М.Т. использует бесконечную ленту памяти. Вообще-то да, ну а так нет. Если у меня в машине хард на 750 гигов, и не резиновый что бы впихнуть туда бесконечную ленту памяти. Я как-то смотрю на понятие алгоритм с точки зрения: возможно ли это реализовать программно, и не подстроить это под чью-то там теорию. И еще, заметьте разницу. 1. Построить алгоритм проверки любого алгоритма на конечность. 2. Показать что в парадигме м.Т. это невозможно. Вот мы берем какой-то алгоритм, пусть даже ошибочный. И запускаем, в итоге он зациклился(завис). Где спрашивается вывод? Цитата: «Алгоритм — это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность». (Д. Э. Кнут) Но, если данный алгоритм мы сначала преобразуем на метамашине в другой, и запустим уже преобразованный. Он будет работать так же как и изначальный, но если изначальный алгоритм зациклился, то преобразованный выдаст вывод: "Результата нет, алгоритм зациклился" и закончит работу. [Ответ][Цитата]
daner Сообщений: 4593	На: Счетность вещественных чисел Добавлено: 09 сен 10 3:01 Цитата: Автор: Весёлый Роджер Вообще-то да, ну а так нет. Если у меня в машине хард на 750 гигов, и не резиновый что бы впихнуть туда бесконечную ленту памяти. Я как-то смотрю на понятие алгоритм с точки зрения: возможно ли это реализовать программно, и не подстроить это под чью-то там теорию. И еще, заметьте разницу. 1. Построить алгоритм проверки любого алгоритма на конечность. 2. Показать что в парадигме м.Т. это невозможно. Заметьте разницу: не любого алгоритма, а только того, который создан для детерминированной МТ, с конечной памятью. Вообще, у обычного алгоритма есть понятие Ввод/Вывод которые не вписываются в вашу теорему, и больше соответствуют бесконечной ленте.И уж тем более, если рассуждать про "реализовать программно", ваш вариант даже близко под это определение не подходит (EXP). [Ответ][Цитата]
Весёлый Роджер Сообщений: 62	На: Счетность вещественных чисел Добавлено: 10 сен 10 3:28 Цитата: Автор: daner Заметьте разницу: не любого алгоритма, а только того, который создан для детерминированной МТ, с конечной памятью. Постараюсь объяснить развернуто, что бы не было, что вы вы говорите про Петра, а я про Ивана. Рассматривая теорию алгоритмов и методы практической реализации алгоритмов - наткнулся на ту штуку, что это совершенно разные вещи, хотя рассматривают одно и тоже. Почему так получилось? Наверное, исторически сложилось... Говорите что мой метод только для детерминированной МТ с конечной памятью. И это верно. Но давайте по порядку что есть что: 1. Конечная память. Где вы видели что бы что нибудь в этом Мире было бы бесконечно?(пример если не согласны). Под какую бы машину мы не писали бы приложение, нам в любом случае дана грань памяти, которую нельзя перепрыгнуть. А бесконечная память в реале не бывает, а лишь в теоретических фантазиях, знание которых не имеет никакого практического применения. Навыдумывать можно все что угодно, если бесконечная лента (а с бесконечностью можно крутить как хошь). В пример: А если обобщить на R^2, дать бесконечную плоскость, в которой головка может ходить и вдоль и поперек. А если ваще по мощности обобщить - если дана машина с бесконечным числом бесконечных лент с бесконечным количеством головок, взаимоуправляемых друг другом - теоретическая бомба, а если еще сделать ее не детерминированной - мозги уедут, древом решений тут не отделаешься... 2.Детерминированность. НМТ - да уж... стою на распутье дорог и думаю куда пойти: налево или направо. И тут идея: зачем думать, я пойду и налево и направо одновременно. Это можно разве что своему психиатру рассказать... Не, конечно встречаются задачки в которых нужно применить многозначную рекурсию или те же методы динамического программирования, визуально говоря: где нужно найти оптимальный путь по графу, и поэтому рассматриваем их все, если получается инфу определить в сжатом виде (в полиномиальной памяти, преодолев экспоненциальную сложность) то хорошо. Компьютер - это и есть детерминированная МТ с конечной памятью. А алгоритмом я считаю что возможно реализовать на компьютере и только. А то что якобы считается алгоритмом только в теоретических сказках - для меня не алгоритм. Цитата: Вообще, у обычного алгоритма есть понятие Ввод/Вывод которые не вписываются в вашу теорему, и больше соответствуют бесконечной ленте. И уж тем более, если рассуждать про "реализовать программно", ваш вариант даже близко под это определение не подходит (EXP). Да ну. Извиняюсь, конечно, по себе замечал, что мне гораздо легче запрогать машину, чем объяснить человеку как это дело запрогать. Но теорему которою написал выше постараюсь описать на примере: Даны два бита памяти: Первый бит - Илья Муромец - готов к бою(1), запарился биться(0). Второй бит - Змей Горыныч - жив(1), мертв(0). Входная информация: 11. Пошел Илья странствовать (выполняется алгоритм) и тут подходит к распутью дорог (условный переход), там надпись на камне: "Налево пойдешь жизнь потеряешь, направо пойдешь вообще армагедон"(если первый бит 1 - пойдет направо, иначе налево). Пошел Илья направо, и дальше и дальше, перерезал половину заморской орды, шел, шел и тут опять тот же камень и пришел к нему и опять готов к бою, змей Горыныч не убит (с тем же состоянием памяти - 11). И поэтому, он снова пойдет по той же дороге и опять вернется в тому же камню бесконечное число раз. И никогда не вернется домой (конец алгоритма), показав мертв ли змей Горыныч (вывод алгоритма). Но если следить "из вне" (доп. алгоритмом со своей памятью) то можно засечь момент когда алгоритм на то же шаг прошел с тем же состоянием памяти, то можно избежать зацикливания вычислительного процесса - обнаружив это и закончить программу. Приведенный мной в предпредыдущем сообщении самый наитупейший. Возможно фиксировать точки используя динамическую память, а так же сжатие информации, а так же вероятностные алгоритмы нахождения точек зацикливания и т.п. да бы снизить вычислительную сложность... Но то что любой алгоритм, который можно реализовать на компьютере, можно проверить на компьютере: "зациклится он или нет", единым алгоритмом, по той же теореме, который не зациклится и в любом случае выдаст "конец алгоритма" - есть факт. [Ответ][Цитата]
daner Сообщений: 4593	На: Счетность вещественных чисел Добавлено: 10 сен 10 15:11 Цитата: Автор: Весёлый Роджер Постараюсь объяснить развернуто, что бы не было, что вы вы говорите про Петра, а я про Ивана. Рассматривая теорию алгоритмов и методы практической реализации алгоритмов - наткнулся на ту штуку, что это совершенно разные вещи, хотя рассматривают одно и тоже. Почему так получилось? Наверное, исторически сложилось... Это тоже самое, что сказать... типа реальная инженерия не имеет никакого отношение к теоретической физики. ИМЕЕТ, просто надо уметь применять. У каждой теоремы, есть свои условия и ограничения. И реальную ситуацию необходимо проверять на эти условия прежде чем использовать эти теоремы. Цитата: Говорите что мой метод только для детерминированной МТ с конечной памятью. И это верно. Но давайте по порядку что есть что: 1. Конечная память. Где вы видели что бы что нибудь в этом Мире было бы бесконечно?(пример если не согласны). Под какую бы машину мы не писали бы приложение, нам в любом случае дана грань памяти, которую нельзя перепрыгнуть. А бесконечная память в реале не бывает, а лишь в теоретических фантазиях, знание которых не имеет никакого практического применения. Неее далеко не так. В реальном мире на много больше "бесконечного" чем в теоретическом. Я имею ввиду то, что чаще всего когда речь идет о больших числах нам уже все-равно, бесконечно это или просто очень много (долго, далеко, и т.д.) Что касается компьютера, то как я уже сказал, ввод/вывод делают компьютер открытой системой с точки зрения данных. Это не соответствует МТ, но в МТ компенсируется предположением бесконечности ленты. Ваш алгоритм не будет работать с программой которая имеет операторы ввода/вывода, так как в этом случае состояние программы не ограничивается только состоянием оперативной памяти, но так же и состоянием внешней среды, которую в легкую можно считать бесконечной. Цитата: Навыдумывать можно все что угодно, если бесконечная лента (а с бесконечностью можно крутить как хошь). В пример: А если обобщить на R^2, дать бесконечную плоскость, в которой головка может ходить и вдоль и поперек. А если ваще по мощности обобщить - если дана машина с бесконечным числом бесконечных лент с бесконечным количеством головок, взаимоуправляемых друг другом - теоретическая бомба, а если еще сделать ее не детерминированной - мозги уедут, древом решений тут не отделаешься... Все верно, но для этого и существуют теоретические исследования. И как ни странно, все эти варианты (о которых вы говорите) рассматривались и имеют доказательства вычислительной эквивалентности самому простому варианту МТ. Цитата: 2.Детерминированность. НМТ - да уж... стою на распутье дорог и думаю куда пойти: налево или направо. И тут идея: зачем думать, я пойду и налево и направо одновременно. Это можно разве что своему психиатру рассказать... Можете психиатру, а можете ... например тем кто занимается квантовыми вычислениями. Мат.модель квантового компьютера наиболее близка именно НДМТ (конечно с определенными ограничениями). Цитата: Не, конечно встречаются задачки в которых нужно применить многозначную рекурсию или те же методы динамического программирования, визуально говоря: где нужно найти оптимальный путь по графу, и поэтому рассматриваем их все, если получается инфу определить в сжатом виде (в полиномиальной памяти, преодолев экспоненциальную сложность) то хорошо. Это несколько другое. Цитата: Компьютер - это и есть детерминированная МТ с конечной памятью. Почти. разница все-же существует. В основном, в возможности ввода/вывода. Цитата: А алгоритмом я считаю что возможно реализовать на компьютере и только. А то что якобы считается алгоритмом только в теоретических сказках - для меня не алгоритм. Это ваша проблема. Но согласитесь, вы не можете спорить с теоремой в которой этот термин используется в несколько другом смысле . Цитата: Да ну. Извиняюсь, конечно, по себе замечал, что мне гораздо легче запрогать машину, чем объяснить человеку как это дело запрогать. Знакомо . Цитата: Но теорему которою написал выше постараюсь описать на примере... Не знаю как другим, а я без примера нормально понял. Но спасибо за пояснения. Цитата: Но то что любой алгоритм, который можно реализовать на компьютере, можно проверить на компьютере: "зациклится он или нет", единым алгоритмом, по той же теореме, который не зациклится и в любом случае выдаст "конец алгоритма" - есть факт. Как я уже писал, это не так. Условием должно быть отсутствие операторов ввода/вывода. Кроме этого, если говорить о реальной применимости, не важно как вы оптимизируете счетчики вашего алгоритма, его выч.сложность будет зависеть от выч.сложности проверяемого алгоритма (в худшем случае), соответственно, если алгоритм имеет экспоненциальную сложность относительно начальных данных и только в конце имеет петлю зацикливания.... мы просто не дождемся за всю нашу жизнь результатов вашего алгоритма. Как по мне, так это делает ваш алгоритм скорее теоретическим, чем практическим, а с теоретической точки зрения, он имеет весьма сильное условие своего применения. [Ответ][Цитата]
VGΨ Сообщений: 666	На: Счетность вещественных чисел Добавлено: 10 сен 10 18:01 Цитата: Автор: гость гост 88.215Ψ, Я готов с вами обсудить проблему остановки, если вы создадите для этого отдельную тему. Но касательно проблемы, обсуждаемой в этом разделе, я уже написал все выше. спасибо, но я не готов, по причине нехватки свободного времени, выступить заводчиком отдельной темы, да и спасибо Данеру с В.Роджером кое что я из обсуждения надеюсь понял. Цитата: Автор: daner А "свобода воли" -- это вообще не из этой оперы. несоглашусь, что это совсем никак не связано. естественый интеллект работает тоже по некоторым алгоритмам, и вопрос о их детерминированости, можно понимать как свободу воли, отсюда естественая паралель к недетерминированным алгоритмам для ИИ, так что в этом понимании "свобода воли" некоторое отношение к теме нашего разговора всеже имеет. Но если вы Данер, исходили из понимания свободы воли в философских традициях, тогда согласен это действительно другая опера. Цитата: Автор: Весёлый Роджер Если при выполнении алгоритма, определенный шаг алгоритма выполнялся дважды при одинаковых состояниях алгоритма, то при заданных входных данных данный алгоритм - не достигнет конца. есть еще одна возможность, если алгоритм генерирует некоторую прогресию, то вероятно он будет работать бесконечно но у него не будет повторов по состоянию, потому как например если состояние это число, то это число будет увеличиваться стремясь к бесконечности. ...да естествено в этом случае нужна бесконечная память ...я помню вы говорили о ограничениях на память :-) [Ответ][Цитата]
daner Сообщений: 4593	На: Счетность вещественных чисел Добавлено: 11 сен 10 2:59 Цитата: Автор: гост 88.215Ψ несоглашусь, что это совсем никак не связано. естественый интеллект работает тоже по некоторым алгоритмам, и вопрос о их детерминированости, можно понимать как свободу воли, отсюда естественая паралель к недетерминированным алгоритмам для ИИ, так что в этом понимании "свобода воли" некоторое отношение к теме нашего разговора всеже имеет. Но если вы Данер, исходили из понимания свободы воли в философских традициях, тогда согласен это действительно другая опера. я просто хотель сказать, что "свобода воли" подразумевает осмысленное принятые решения, так как принимающий несет на себе ответственость за последствия своих действий (за некоторые ему светит длительное наказатенее в очень теплом месте). Так что, как мне кажется, случайный выбор -- не имеет отношение к "свободе воли". Для меня, "свобода воли" в альгоритме начинается тога, когда происходит оценка возможных вариантов достижения цели, осознание последствий применения этих вариантов в текущей ситуации и выбор наиболее приемлемого, на основе полученного прежде опыта. [Ответ][Цитата]
Стр.5 (6): 1  2  3  4  [5]  6 << < Пред. | След. > >>