ВАШЕ СВИДЕТЕЛЬСТВО
О ПУБЛИКАЦИИ В СМИ И РЕЦЕНЗИЯ
бесплатно за 1 минуту
Добавить материал
Количество Ваших материалов: 0.
Авторское
свидетельство о публикации в СМИ
добавьте 1 материал
Свидетельство
о создании электронного портфолио
добавьте 5 материала
Секретный
подарок
добавьте 10 материалов
Грамота за
информатизацию образования
добавьте 12 материалов
Рецензия
на любой материал бесплатно
добавьте 15 материалов
Видеоуроки
по быстрому созданию эффектных презентаций
добавьте 17 материалов
Ахмед Изнауров Свидетельство о публикации Рецензия
Свидетельство Скачивание доступно только автору
Проблема останова, ее неразрешимость

Проблема останова, ее неразрешимость

Формулировка проблемы остановки Пусть у нас есть строка с закодированной функцией A (всё равно на каком языке, это не принципиально). Требуется создать функцию F, которая определит, будет ли функция A выполняться вечно или нет (зависнет или не зависнет). Естественно, работа A зависит от входных данных D. Соответственно F должна принимать на вход две переменных: код функции A и входные параметры D. А возвращатьF(A, D) будет логическое значение: True — A(D) остановится, False — A(D) будет работать вечно. По сути, F(A, D) должна проанализировать строки. Зачем решать задачу остановки? Приведу один пример. Всем, кто знаком с задачами криптографии, известно, какую важную роль в этой дисциплине играют простые числа Мерсенна. Человечество прилагает множество усилий по поиску этих чисел. Последнее (пока самое больше) было обнаружено 6 сентября 2008 года и насчитывало 11185272 десятичных знаков. И прямо сейчас десятки тысяч процессоров работают над поиском новых чисел. Числа Мерсенна напрямую связаны с совершенными числами. Все эти числа пока таят множество загадок (во многом поэтому они и используются для шифрования и сокрытия информации), но мне хотелось бы остановиться только на совершенных числах. Совершенные числа — это такие числа, сумма всех делителей которых равна самому числу. Например 6 делится на 1, 2 и 3; 1+2+3=6. 6 — совершенное число. 28 тоже совершенное число. Не смотря на то, что эти числа активно изучаются теоретиками и на их поиски брошены колоссальные вычислительные мощности, пока так и не понятно, сколько этих чисел, ограниченно ли их количество и существуют ли нечётные совершенные числа. Гипотезы о не-существовании нечётных совершенных чисел и о бесконечном их количестве считаются одними из гипотез, особо остро требующих доказательства или опровержений. Программу, которая ищет совершенные числа написать очень просто. Вот пример кода на Python: def perfect_number(): for n in xrange(1, 500): if sum(filter(lambda x: n % x == 0, xrange(1, n))) == n: print "%5d is perfect number" % n perfect_number()

  • Научно-исследовательская работа
  • Научные работы
  • Образовательные программы
  • Повышение квалификации
  • Подготовка к тестированию
  • Информатика
  • Высшее образование

Все файлы материала:
закрыть
НОВОЕ СООБЩЕНИЕ
Администрация «Знанио»
Здравствуйте, проверьте свои знания
во Всероссийских педагогических тестированиях:

- выберите тему
- пройдите небольшой тест
- получите СЕРТИФИКАТ ОТЛИЧИЯ