antony_w (antony_w) wrote,
antony_w
antony_w

Математик Теренс Тао обогнал компьютер в решении проблемы несоответствия Эрдеша



Математик Теренс Тао решил так называемую проблему несоответствия Пала Эрдеша. Предыдущее ее решение, полученное в течение шести часов компьютером, представляет собой файл объемом 13 гигабайтов, что на три гигабайта больше, чем весь текстовый архив Wikipedia. Свои результаты исследований Тао опубликовал на сайте arXiv.org, а кратко с ними знакомит издание New Scientist.

Проблема несоответствия Эрдеша формулируется следующим образом. Пусть дана бесконечная последовательность, элементами которой выступают только числа -1 и +1. Из нее можно выделить подпоследовательность, содержащую конечное число таких элементов. Их сумма будет давать число, называемое несоответствием. Несоответствие определяет внутренние свойства подпоследовательности и исходной последовательности.

Эрдеш полагал, что у любой бесконечной последовательности, состоящей из -1 и +1, всегда найдется конечная подпоследовательность, несоответствие которой будет больше, чем любое выбранное число. Ученый не доказал свое утверждение, однако (как часто делал) в 1930 году предложил за него премию в 500 долларов.

В 2012 году математики российского происхождения, работающие в Ливерпульском университете в Великобритании, предложили компьютерный вариант доказательства утверждения Эрдеша. Они рассмотрели частный случай конечной подпоследовательности из 1161 членов, а компьютер за шесть часов работы выдал файл размером 13 гигабайтов, из которого следовало, что бесконечная последовательность всегда будет иметь несоответствие больше 2.

Доказательство Тао из Калифорнийского университета в Лос-Анджелесе заняло 20 страниц текста (вместе с титульным листом и списком литературы). Аргументы математика использовали специального вида гипотезу Эллиота-Халберстама (о распределении простых чисел в арифметической прогрессии), а также данные, полученные в проекте Polymath5 — добровольного объединения ученых, которые с помощью технологий типа Wikipedia и блогов совместно работали над доказательством проблемы несоответствия.

Австралийский и американский математик Теренс Тао родился в 1975 году в городе Аделаида. В 24 года он стал самым молодым профессором Калифорнийского университета в Лос-Анджелесе. В 2006 году на 25-м Международном конгрессе математиков в Мадриде Тао стал лауреатом Филдсовской премии, а в 2014 году — «Премии за прорыв в математике» Юрия Мильнера, Марка Цукерберга и Сергея Брина.

Tags: компьютер, люди
Subscribe

Posts from This Journal “компьютер” Tag

promo antony_w august 17, 2014 11:48 18
Buy for 10 tokens
Есть блог, в котором написано много постов про роботов: ссылка И там есть несколько статей о замене рабочих мест человека роботами: Уже к 2018 году роботы отберут у человека часть профессий Рабский труд без зарплаты Армия роботов: зачем она нужна обильной людьми Поднебесной и кому может…
  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 1 comment