Что нового

Концепция - Решение неразрешимой задачи (!)

XM

Знающий
Сообщения
70
Репутация
8
В теории вычислений доказывается, что так называемая задача останова программы не может быть решена никаким алгоритмом (!).
Формулировка проста: дается описание произвольного алгоритма на каком-либо формальном языке (например, на AutoIt). За конечное время требуется определить, закончит ли этот алгоритм работу или будет продолжать выполняться бесконечно долго.

К примеру:
Код:
N = J
ПОКА N не является совершенным числом
    N = N + 2
Конец цикла.

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

Для справки: совершенные числа - это числа, равные сумме всех своих делителей, кроме себя. (6=3+2+1)

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

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

Так, выше я отметил, что переменная N может хранить любое число. Если же рассмотреть более реалистичный сценарий и предположить, что N представляет собой беззнаковую 32-разрядную переменную, то окажется, что как только значение N превысит 2^32 - 1 (2 в степени 32), произойдет переполнение.

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

Задание заключается в решении задачи останова для произвольной программы (в данном случае AutoIt).

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

Интересно почитать мнения участников форума по этому вопросу...
 

SyDr

Сидра
Сообщения
651
Репутация
158
Странно... Впрочем ладно...

1) Можно устанавливать пределы для вычислений. К примеру, если число для обработки превышает некоторый заданный предел - считать, что решений больше нет.
2) Можно устанавливать таймер. Если за заданное время не было найдено ни одного нового решения - считать, что решений боьше нет.
3) Концепция, если выполняется та же самая строка и все переменные имеют те же значения, применима только для вычислительных задач. Если есть какой-то элемент случайности (Random или что-то другое) - то два одинаковых состояния программы не означает, что это бесконечный цикл.
 

seriych

Новичок
Сообщения
18
Репутация
0
Vendor сказал(а):
В теории вычислений доказывается, что так называемая задача останова программы не может быть решена никаким алгоритмом (!).
Формулировка проста: дается описание произвольного алгоритма на каком-либо формальном языке (например, на AutoIt). За конечное время требуется определить, закончит ли этот алгоритм работу или будет продолжать выполняться бесконечно долго.
Вообще это формулируется для всех алгоритмов. То есть говориться, что нельзя создать единый универсальный алгоритм, работающий для любой программы/алгоритма. Для каждой конкретной программы нужный алгоритм уже может существовать. ИМХО конечность реальных переменных роли не играет.
 

AZJIO

Меценат
Меценат
Сообщения
2,874
Репутация
1,194
Vendor
1. Задача останова решается нажатием кнопки выключения на корпусе ПК в течении 4 сек.
2. Если мощность проца стремится к бесконечности, то вопрос, к чему стремится точка останова? Если задача имеет решение, то точка останова стремится к нулю.
3. Кстати, какое практическое применение имеет данная задача, кроме надуманных свойств/атрибутов объекта?
 
Автор
X

XM

Знающий
Сообщения
70
Репутация
8
seriych сказал(а):
Вообще это формулируется для всех алгоритмов...

Ну вообще да, так оно и есть.


Добавлено:
Сообщение автоматически объединено:

AZJIO сказал(а):
1. Задача останова решается нажатием кнопки выключения на корпусе ПК в течении 4 сек.
Совершенно верно! :smile:
А кстати, почему именно 4 сек.?
2. Если мощность проца стремится к бесконечности, то вопрос, к чему стремится точка останова? Если задача имеет решение, то точка останова стремится к нулю.
Это утверждение не может быть применено в данном случае. Точка останова не стремится к нулю.
3. Кстати, какое практическое применение имеет данная задача, кроме надуманных свойств/атрибутов объекта?
В принципе в данном контексте никакого. Просто, так сказать, размышления... :smile:
 

AZJIO

Меценат
Меценат
Сообщения
2,874
Репутация
1,194
Vendor
Это утверждение не может быть применено в данном случае. Точка останова не стремится к нулю.
Представим требуемое бесконечно большое количество тиков проца необходимое для решения задачи.
Теперь представим бесконечно мощный проц, выполняющей бесконечное количество операций за бесконечно короткое время. Представил?
Тепер решаем: бесконечность тиков задачи делим на бесконечность мощи проца, получаем 1. Т.е. за одну микросекунду бесконечная задача будет решена и наступит точка останова...
 
Автор
X

XM

Знающий
Сообщения
70
Репутация
8
AZJIO сказал(а):
Тепер решаем: бесконечность тиков задачи делим на бесконечность мощи проца, получаем 1. Т.е. за одну микросекунду бесконечная задача будет решена и наступит точка останова...

Ну суть я уловил. Весьма лаконичное решение...
 

amel27

Продвинутый
Сообщения
146
Репутация
55
AZJIO [?]
Теперь представим бесконечно мощный проц
не путайте "физику" с "математикой":

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

AZJIO

Меценат
Меценат
Сообщения
2,874
Репутация
1,194
amel27
определяющий существование/отсутствие этого останова
Так эти свойства были заданы в предыдущем посте, где говорилось о решаемости задачи.

Следующий ход наверно будет наделение объекта новыми свойствами, с вытекающим продолжением ...
 

amel27

Продвинутый
Сообщения
146
Репутация
55
AZJIO [?]
эти свойства были заданы в предыдущем посте, где говорилось о решаемости задачи.

"бесконечно большое количество тиков проца" не является решением, в условии недвусмысленно сказано про "конечное количество" тиков (оно же "время")
 

kaster

Мой Аватар, он лучший самый
Команда форума
Глобальный модератор
Сообщения
4,020
Репутация
626
AZJIO
не хочу расстраивать, но одна бесконечность деленная на другую не есть 1. тем более мс ;D


Добавлено:
Сообщение автоматически объединено:

Vendor [?]
В принципе в данном контексте никакого. Просто, так сказать, размышления...
дык это, принял к сведению
 

Yashied

Модератор
Команда форума
Глобальный модератор
Сообщения
5,379
Репутация
2,724
Vendor сказал(а):
Интересно почитать мнения участников форума по этому вопросу...

Если ты смотрел фильм "Аватар", то наверняка помнишь, какая фраза там больше всего произносилась: "Полная хрень".

Vendor сказал(а):
Моя концепция такова...

Если под хранение каждого состояния программы выделить как минимум 1 байт, то для 2^32 - 1 состояний необходимый размер памяти будет составлять ~4 ГБ, и переполнение будет уже в другом.

Kaster сказал(а):
...не хочу расстраивать, но одна бесконечность деленная на другую не есть 1.

Ну, если он исходил из теории пределов :smile:, то такая неопределенность может быть и 1. Если я не ошибаюсь, то есть там такое правило Лопиталя... Давно это было. А вот с размерностью он не ошибся.

AZJIO сказал(а):
...бесконечность тиков задачи делим на бесконечность мощи проца, получаем 1. Т.е. за одну микросекунду бесконечная задача будет решена и наступит точка останова...

Т.е. количество тиков (Гц) делим на "мощь" (Гц/с), получаем время.

А если серьезно, то любое переполнение должно учитываться на стадии написания программы, и весь этот разговор не что иное, как "Полная хрень". Например в WinAPI полно функций, где переполнение есть нормальное явление, например GetTickCount().
 
Автор
X

XM

Знающий
Сообщения
70
Репутация
8
Yashied сказал(а):
Vendor сказал(а):
Интересно почитать мнения участников форума по этому вопросу...

Если ты смотрел фильм "Аватар", то наверняка помнишь, какая фраза там больше всего произносилась: "Полная хрень".

Vendor сказал(а):
Моя концепция такова...

Если под хранение каждого состояния программы выделить как минимум 1 байт, то для 2^32 - 1 состояний необходимый размер памяти будет составлять ~4 ГБ, и переполнение будет уже в другом.

Kaster сказал(а):
...не хочу расстраивать, но одна бесконечность деленная на другую не есть 1.

Ну, если он исходил из теории пределов :smile:, то такая неопределенность может быть и 1. Если я не ошибаюсь, то есть там такое правило Лопиталя... Давно это было. А вот с размерностью он не ошибся.

AZJIO сказал(а):
...бесконечность тиков задачи делим на бесконечность мощи проца, получаем 1. Т.е. за одну микросекунду бесконечная задача будет решена и наступит точка останова...

Т.е. количество тиков (Гц) делим на "мощь" (Гц/с), получаем время.

А если серьезно, то любое переполнение должно учитываться на стадии написания программы, и весь этот разговор не что иное, как "Полная хрень". Например в WinAPI полно функций, где переполнение есть нормальное явление, например GetTickCount().

Мда... Возникают такие ощущения, что вы не в институтах учились, а прямо в каких-то "духовных семинариях" право... :smile: Ловко уходите от проблем..))
Ну да ладно, тема закрыта. (для вас по крайней мере))))
 

Yashied

Модератор
Команда форума
Глобальный модератор
Сообщения
5,379
Репутация
2,724
Vendor, Вы слишком надменно себя ведете и откровенно проявляете неуважение к другим участникам форума. Это касается не только этой ветки. Подумайте над этим, даю Вам бан на 29 дней. Почему 29, см. ниже (by Valik):

Код:
MsgBox(0, '', Random(1, 60, 1))
 
Верх