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

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

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

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

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

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

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

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

Lenta.ru

Похожие новости:
В Стэнфордском университете создают живой компьютер
Американцы решили совместить технологии и медицину в одном компьютере. Они работают над электронным устройством на основе ДНК живых организмов. Первая деталь уже готова - биологический транзистор. По словам ученых, он работает гораздо лучше, чем электронные аналоги. Созданный элемент являет собой воплощение нано-технологического ..
2013-03-30 1389 0 Разное, интересное
0
Будущее глазами футуролога из Google. Бессмертие – только начало
Американский футуролог и технический директор Google Рэй Курцвейл знаменит во всем мире. Популярность ему принесли книги, посвященные будущему технологий и человечества. Он доказал, что человеческий прогресс стремительно пошел вверх с появлением технологий распознавания речи.И вот новое сенсационное заявление Рэймонда Курцвейля ..
2016-04-11 2073 0 Разное, интересное
0
Фотографу пересадили вместо глаза камеру
Таня Влач, фотограф из Сан-Франциско. Она лишилась левого глаза в автокатастрофе. И теперь решилась на уникальную операцию, когда вместо потерянного глаза ей будет встроена мини-кинокамера... Операция стоит 15000 долларов. Новое устройство позволит Тане записывать самые интересные ..
2012-06-26 1704 0 Разное, интересное
0
Насколько умён искусственный интеллект?
...Как выясняется, пока не слишком: экспериментальная компьютерная система ConceptNet 4 по «умственным» способностям может сравниться разве что с четырёхлетним ребёнком. Как далеко зашли технологии развития искусственного интеллекта (ИИ)? Задавшись этим вопросом, специалисты из Иллинойсского университета в Чикаго (США), ..
2013-07-17 1425 0 Разное, интересное
0
Компьютерный сбой помог Deep Blue победить Каспарова
В 1997 году Гарри Каспаров проиграл шахматный матч компьютеру Deep Blue. В первой партии матча компьютер сделал ход, который вывел Каспарова из равновесия и заставил экспертов говорить о скрытой силе искусственного интеллекта. Поражение Каспарова навсегда ..
2012-10-5 1314 0 Разное, интересное
0
Ученый утверждает, что изобрел машину для предсказания будущего
Иранский 27-летний ученый Али Разеги запатентовал изобретение "Машина времени Арйяйек" в центре стратегических инноваций Ирана, сообщает британская газета Daily Telegraph. По словам ученого, эта машина не переносит пользователя в будущее, а предсказывает его на пять-восемь лет вперед по отпечаткам пальцев. "Мое ..
2013-04-11 1982 0 Разное, интересное
0
С помощью микроволновки изучат ДНК и радиоактивные изотопы
Разработанная американскими инженерами модификация обыкновенной СВЧ-печи позволит уничтожать опасные материалы (от вирусов до метамфетамина), оставляя возможность изучать ДНК или химический состав ликвидированного вещества, сообщается в пресс-релизе Окриджской национальной лаборатории. Новый инструмент криминалистов и дезинфекторов состоит из двух микроволновок. ..
2014-09-18 1104 0 Разное, интересное
0
Британские ученые создали самый реалистичный аватар
Ученые Кембриджского университета совместно с японскими коллегами создали самый реалистичный аватар. Первая электронная девушка получила имя Зои. Она может произнести любой текст, введенный в компьютер, с заданной эмоциональной окраской. Возможно, в будущем Зои и ее сестры заменят учителей в школах ..
2013-04-3 1191 0 Разное, интересное
0
Миллионер из России создаст бессмертного киборга
В субботу 15 июня этого года представитель проекта ”Россия 2045” Дмитрий Ицков собрал лучшие умы мира и несколько роботов в Нью-Йорке для обсуждения вопросов бессмертия. Ицков, выглядящий моложе своих 32 лет, представил четкое расписание этапов для достижения поставленной цели: ..
2013-06-18 2131 0 Разное, интересное
0
Человек доказал свое превосходство над компьютером в безлимитном покере
Двухнедельный турнир по покеру между лучшей компьютерной программой и четырьмя профессионалами (из первой десятки рейтинга лучших игроков мира) закончился победой человека. Разработанная в Университете Карнеги-Меллон программа Claudico проиграла в безлимитный техасский холдем около 732 тысяч долларов. ..
2015-05-12 1435 0 Разное, интересное
-1
Бессмертие изобретут через год
Во вторник в "Комсомольской правде" прошла пресс-конференция, приуроченная к приезду англичанина Найджела Экланда - одного из немногих в мире инвалидов с бионическим протезом. "Все, что мне нужно, - это представить, что я сжимаю шарик. Или еду на мотоцикле", - рассказывал Экланд, демонстрируя свою руку, кисть которой то сжималась, то разжималась. ..
2015-03-22 2221 0 Разное, интересное
1
Стимуляция мозга поможет развить когнитивные навыки
Университет Пенсильвании выяснил, как можно мобилизовать интеллектуальные ресурсы мозга. Ученые собрали группу из 11 человек, которые согласились на глубокую электростимуляцию мозга. У всех добровольцев была болезнь Паркинсона. Стимуляции подвергалась так называемая черная субстанция мозга. Эта зона важна для регулирования ..
2014-05-20 1907 0 Разное, интересное
0
Девять мифов и фактов о молнии
Ученые изучают молнию на протяжении сотен лет. Хотя они прекрасно знают, что вызывает молнии, эти загадочные вспышки электричества хранят еще много секретов. Учитывая, что летом начался сезон отпусков, мы предлагаем вам пополнить копилку ваших знаний полезными и интересными фактами о молниях. ..
2013-12-12 1700 0 Разное, интересное
1
Ученые изучают наш мир на виртуальность
Ученые физики из США и Великобритании нашли способ проверки того, живем ли мы в реальном мире или в виртуальной реальности, созданной нашими дальними потомками. Профессор физики Университета штата Вашингтон Мартин Сэвидж со своим аспирантом Зоре Давуди и Сайласом Бином из Университета Нью-Хемпшира ..
2013-01-8 2773 0 Разное, интересное
0
Персональный компьютер был создан и запатентован в СССР
Впервые устройство, которое мы сегодня называем Персональным Компьютером, было изобретено в СССР в 1968 году, за несколько лет до его повторного «изобретения» в США. Кстати, сотовый телефон тоже довольно давно изобрели в СССР... Персональный компьютер был создан и запатентован в СССР за 8 лет до Apple Горохов Арсений ..
2013-07-17 4351 0 Разное, интересное
1