Машина Тьюринга

Тема в разделе "WASM.HEAP", создана пользователем gradient, 12 окт 2006.

  1. gradient

    gradient New Member

    Публикаций:
    0
    Регистрация:
    10 окт 2006
    Сообщения:
    30
    Являются ли процессоры Pentium>=3-машинами Тьюринга?
     
  2. EvilsInterrupt

    EvilsInterrupt Постигающий азы дзена

    Публикаций:
    0
    Регистрация:
    28 окт 2003
    Сообщения:
    2.428
    Адрес:
    Russia
    gradient
    А что такое Машина Тюринга вообще?

    Это Абстрактное Математематическое понятие, служащее лишь для того чтобы доказаывать разрешимость того или иного алгоритма( по задумке Автора Алана Тюринга).
     
  3. Sharp

    Sharp New Member

    Публикаций:
    0
    Регистрация:
    1 авг 2003
    Сообщения:
    143
    Адрес:
    Ukraine
    Наверно, вопрос был относительно Тьюринг-полноты процессоров? Да, если не учитывать бесконечность ленты Тьюринга, процессоры Тьюринг-полные, т.к. могут исполнять другую машину Тьюринга.
     
  4. Quantum

    Quantum Паладин дзена

    Публикаций:
    0
    Регистрация:
    6 янв 2003
    Сообщения:
    3.143
    Адрес:
    Ukraine
    gradient
    3й пень нельзя обозвать предельно простым символьным прибором. Зато его можно (чисто теоретически) воплотить на базе универсальной машины Тьюринга.
     
  5. gradient

    gradient New Member

    Публикаций:
    0
    Регистрация:
    10 окт 2006
    Сообщения:
    30
    У пней выше третьего, по моему, есть предиктор ветвлений. Вписывается ли это в определение МТ?
     
  6. Noble Ghost

    Noble Ghost New Member

    Публикаций:
    0
    Регистрация:
    28 апр 2004
    Сообщения:
    204
    Адрес:
    Russia
    Насколько я помню, язык считается тьюринг-полным, если в нем присутствует команда условного перехода и команда логического сдвига.
    Язык ассемблера x86 их содержит...
    Причем тут предиктор ветвлений, как он может нарушить тьюринг-полноту? =)
     
  7. gradient

    gradient New Member

    Публикаций:
    0
    Регистрация:
    10 окт 2006
    Сообщения:
    30
    Я, конечно, точно не знаю, но тут попахивает искуственным интелектом.
    Ведь, по сути, машина юзает юзера, который генерит события и тем ,самым, условные переходы!
     
  8. Ustus

    Ustus New Member

    Публикаций:
    0
    Регистрация:
    8 авг 2005
    Сообщения:
    834
    Адрес:
    Харьков
    Предиктор переходов - это всего лишь внутренняя фича, с математической точки зрения совершенно прозрачная. (спроси leo, он тебе расскажет что там не то что искусственным, а иногда и никаким интеллектом не пахнет.) То же самое относится к кешу, TLB, Out-of-Ordering, superscalar и прочим потугам выжать побольше из одного гигагерца.
    не одна из этих заморочек не меняет алгоритмы работы процессора, если он исправен, конечно. Но построить математическую модель неисправного процессора - вот достойная задача! :):)
     
  9. gradient

    gradient New Member

    Публикаций:
    0
    Регистрация:
    10 окт 2006
    Сообщения:
    30
    Согласен, что внутреняя фича, согласен, что статистика маленькая. Но это только пока... Но дело в том, что программер не может это программировать!
    Процессор сам знает как ему лучше...
     
  10. Ustus

    Ustus New Member

    Публикаций:
    0
    Регистрация:
    8 авг 2005
    Сообщения:
    834
    Адрес:
    Харьков
    А программист знает, как сделать ему хуже :)
    Машину Тьюринга не интересует ее внутренне устройство. У любого алгоритма есть вход и выход. И у процессора есть вход и выход. А что внутри - не имеет значения. Внутри Pentium4, Athlon64 и Core2 не имеют практически ничего общего, что не мешает им одинаково себя вести с алгоритмической точки зрения.
     
  11. gradient

    gradient New Member

    Публикаций:
    0
    Регистрация:
    10 окт 2006
    Сообщения:
    30
    Насколько я знаю машина Тьюринга определяется своим внутренним устройством.

    Это спорное заявление... Регистры, АЛУ -много общего.
    Как черный ящик они ведут себя одинаково, но если посмотреть внимательно, то не совсем. Да взять хотя бы тот же тест на скорость . Всегда ли у тебя при повторном тестировании равные значения получались? Это усугубляется промахами, ошибками предсказания.
    Это , конечно, только начало... войны миров. Мне кажется.
     
  12. sergh

    sergh New Member

    Публикаций:
    0
    Регистрация:
    31 авг 2005
    Сообщения:
    128
    Адрес:
    rsdn
    С точки зрения математики и машины Тьюринга, нет такого понятия как скорость выполнения элементарной операции. И способ выполнения элементароной операции тоже не важен. И даже то, что внутри операции выполняются не в том же порядке, в каком они идут в коде, тоже ни кого не волнует :)

    Все упомянутые процессоры (Atlon, P4 и т.п.) имеют специфицированный интерфейс - это язык ассемблера x86. Теоретически, тот же самый интерфейс можно реализовать на машине Тьюринга. Это и значит, что за пределы машины Тьюринга никто из них не вышел.
     
  13. Ustus

    Ustus New Member

    Публикаций:
    0
    Регистрация:
    8 авг 2005
    Сообщения:
    834
    Адрес:
    Харьков
    АЛУ - это как раз то место, где они совсем не похожи... :)
    Да и регистровые файлы у них шибко разные...
     
  14. gradient

    gradient New Member

    Публикаций:
    0
    Регистрация:
    10 окт 2006
    Сообщения:
    30
    Может быть вы и правы. Тогда интересный вопрос: что такое не машина Тьюринга(ну короче понятно...). Это уже разум или еще нет?
     
  15. Ustus

    Ustus New Member

    Публикаций:
    0
    Регистрация:
    8 авг 2005
    Сообщения:
    834
    Адрес:
    Харьков
    Встречный интересный вопрос - а что есть разум? :)
    Не машина Тьюринга - это, например аналоговая ЭВМ. Не смейтесь, мы их в институте проходили. И даже лабы делали.
     
  16. gradient

    gradient New Member

    Публикаций:
    0
    Регистрация:
    10 окт 2006
    Сообщения:
    30
    Точно не знаю, наверное- асоциативная память...?

    Это не смешно. По крайней мере float вачисления намного быстрее.

    Вот тут набрел на статью о перспективах железа и фон-неймановской (Тьюринг) архитектуры.

    http://www.osp.ru/text/302/2449832/_p1.html
     
  17. gilg

    gilg New Member

    Публикаций:
    0
    Регистрация:
    19 май 2005
    Сообщения:
    527
    ПЛИСы не являются машиной Тьюринга, но до интеллекта им явно далековато
     
  18. sergh

    sergh New Member

    Публикаций:
    0
    Регистрация:
    31 авг 2005
    Сообщения:
    128
    Адрес:
    rsdn
    ПЛИС - программируемая интегральная схема? А почему ты думаешь, что она не моделируется машиной Тьюринга?
     
  19. gilg

    gilg New Member

    Публикаций:
    0
    Регистрация:
    19 май 2005
    Сообщения:
    527
    sergh
    Ты наверное прав. Разводка ПЛИСов производится на обычных процессорах. А если обычный процессор - это машина Тьюринга, значит он моделирует их работу. Параллельность обработки ввела в заблуждение :)
     
  20. sergh

    sergh New Member

    Публикаций:
    0
    Регистрация:
    31 авг 2005
    Сообщения:
    128
    Адрес:
    rsdn
    Мм.. Про параллельность я не подумал. При желании, параллельность вносит недетерменизм, может это уже и за пределами машины Тьюринга. К сожалению, хреновый из меня математик, не знаю точного определения, только на уровне здравого смысла.