Показано с 1 по 1 из 1.

Двадцатилетний студент решил задачу о машине Тьюринга

  1. #1
    Senior Member Репутация Репутация Репутация Репутация Репутация Репутация Репутация Репутация Репутация Репутация Репутация Аватар для ALEX(XX)
    Регистрация
    31.03.2005
    Адрес
    Чернигов
    Сообщений
    10,777
    Вес репутации
    3708

    Двадцатилетний студент решил задачу о машине Тьюринга

    25 октября 2007 года, 14:53
    Текст: Владимир Парамонов

    Двадцатилетний британский студент Алекс Смит из Бирмингемского университета решил сложную математическую задачу, доказав, что машина Тьюринга с двумя состояниями каретки и алфавитом из трех символов является универсальной.


    Машина Тьюринга (изображение с сайта ArsTechnica)

    Машина Тьюринга, представляющая собой абстрактный исполнитель, была предложена британским математиком Аланом Тьюрингом в 1936 году для формализации понятия алгоритма. В состав машины Тьюринга входит бесконечная в обе стороны лента, разделенная на ячейки, и управляющее устройство (каретка), способное находиться в одном из состояний, число которых точно определено. Каретка может перемещаться влево и вправо по ленте, читать и записывать в ячейки символы некоторого конечного алфавита. При этом управляющее устройство работает в соответствии с набором правил, которые предписывают каретке переместиться на одну клетку, записать символ и т.д. Универсальной называют такую машину Тьюринга, которая может заменить собой любую другую машину Тьюринга.
    Весной нынешнего года известный американский математик Стивен Вольфрам предложил желающим доказать или опровергнуть предположение о том, что машина Тьюринга с двумя состояниями каретки, набором правил и алфавитом из трех символов является универсальной. В качестве приза за решение задачи Вольфрам учредил денежное вознаграждение в размере 25 тысяч долларов США.
    Как теперь сообщает ArsTechnica, первым с поставленной задачей справился Алекс Смит, которому удалось доказать, что предложенная Вольфрамом машина Тьюринга действительно является универсальной. С изысканиями Смита можно ознакомиться здесь (файл в формате PDF).

    compulenta.ru
    Left home for a few days and look what happens...

  2. Будь в курсе!
    Реклама на VirusInfo

    Надоело быть жертвой? Стань профи по информационной безопасности, получай самую свежую информацию об угрозах и средствах защиты от ведущего российского аналитического центра Anti-Malware.ru:

    Anti-Malware Telegram
     

Похожие темы

  1. Ответов: 5
    Последнее сообщение: 25.09.2010, 23:18
  2. Толковый студент
    От SDA в разделе Оффтоп
    Ответов: 56
    Последнее сообщение: 31.10.2009, 14:40
  3. Принтеры HP DeskJet отмечают двадцатилетний юбилей
    От ALEX(XX) в разделе Новости аппаратного обеспечения
    Ответов: 1
    Последнее сообщение: 29.02.2008, 20:44

Свернуть/Развернуть Ваши права в разделе

  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения
  •  
Page generated in 0.01125 seconds with 15 queries