В теории вычислений доказывается, что так называемая задача останова программы не может быть решена никаким алгоритмом (!).
Формулировка проста: дается описание произвольного алгоритма на каком-либо формальном языке (например, на AutoIt). За конечное время требуется определить, закончит ли этот алгоритм работу или будет продолжать выполняться бесконечно долго.
К примеру:
Приведенный алгоритм заканчивает работу, найдя первое нечетное совершенное число (в предположении, что переменная N имеет потенциально неограниченный размер и может хранить любые, сколь угодно большие целые числа).
Для справки: совершенные числа - это числа, равные сумме всех своих делителей, кроме себя. (6=3+2+1)
Ситуация интересна тем, что на сегодняшний день никто не знает, существуют ли вообще нечетные совершенные числа. Поэтому дать определенный (правильный) ответ на вопрос об останове цикла (программы) их поиска весьма затруднительно. Просто запустить программу и проанализировать ее поведение тоже не получится. Если окажется, что нечетных совершенных чисел не существует, мы не сумеем получить ответ за конечное время - программа будет перебирать все целые числа по очереди, а целых чисел, как известно, бесконечное множество.
Как (нам) известно, любая реальная переменная или структура данных имеет ограниченный размер (отличающим их от алгоритмов в математическом смысле).
Так, выше я отметил, что переменная N может хранить любое число. Если же рассмотреть более реалистичный сценарий и предположить, что N представляет собой беззнаковую 32-разрядную переменную, то окажется, что как только значение N превысит 2^32 - 1 (2 в степени 32), произойдет переполнение.
Таким образом, задача останова программы для обычных компьютерных программ решаема за конечное (хотя и, возможно, невероятно долгое) время.
Задание заключается в решении задачи останова для произвольной программы (в данном случае AutoIt).
Моя концепция такова: запись, содержащая текущие значения переменных и идентификатор (номер) выполняемой строки, однозначно описывают состояние программы в данный момент времени. Если при выполнении программы некоторое состояние возникает во второй раз, это означает бесконечный цикл.
Интересно почитать мнения участников форума по этому вопросу...
Формулировка проста: дается описание произвольного алгоритма на каком-либо формальном языке (например, на AutoIt). За конечное время требуется определить, закончит ли этот алгоритм работу или будет продолжать выполняться бесконечно долго.
К примеру:
Код:
N = J
ПОКА N не является совершенным числом
N = N + 2
Конец цикла.Приведенный алгоритм заканчивает работу, найдя первое нечетное совершенное число (в предположении, что переменная N имеет потенциально неограниченный размер и может хранить любые, сколь угодно большие целые числа).
Для справки: совершенные числа - это числа, равные сумме всех своих делителей, кроме себя. (6=3+2+1)
Ситуация интересна тем, что на сегодняшний день никто не знает, существуют ли вообще нечетные совершенные числа. Поэтому дать определенный (правильный) ответ на вопрос об останове цикла (программы) их поиска весьма затруднительно. Просто запустить программу и проанализировать ее поведение тоже не получится. Если окажется, что нечетных совершенных чисел не существует, мы не сумеем получить ответ за конечное время - программа будет перебирать все целые числа по очереди, а целых чисел, как известно, бесконечное множество.
Как (нам) известно, любая реальная переменная или структура данных имеет ограниченный размер (отличающим их от алгоритмов в математическом смысле).
Так, выше я отметил, что переменная N может хранить любое число. Если же рассмотреть более реалистичный сценарий и предположить, что N представляет собой беззнаковую 32-разрядную переменную, то окажется, что как только значение N превысит 2^32 - 1 (2 в степени 32), произойдет переполнение.
Таким образом, задача останова программы для обычных компьютерных программ решаема за конечное (хотя и, возможно, невероятно долгое) время.
Задание заключается в решении задачи останова для произвольной программы (в данном случае AutoIt).
Моя концепция такова: запись, содержащая текущие значения переменных и идентификатор (номер) выполняемой строки, однозначно описывают состояние программы в данный момент времени. Если при выполнении программы некоторое состояние возникает во второй раз, это означает бесконечный цикл.
Интересно почитать мнения участников форума по этому вопросу...
