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

Являются ли процессоры Pentium>=3-машинами Тьюринга?

 

gradient
А что такое Машина Тюринга вообще?

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

 

Наверно, вопрос был относительно Тьюринг-полноты процессоров? Да, если не учитывать бесконечность ленты Тьюринга, процессоры Тьюринг-полные, т.к. могут исполнять другую машину Тьюринга.

 

gradient
3й пень нельзя обозвать предельно простым символьным прибором. Зато его можно (чисто теоретически) воплотить на базе универсальной машины Тьюринга.

 

У пней выше третьего, по моему, есть предиктор ветвлений. Вписывается ли это в определение МТ?

 

Насколько я помню, язык считается тьюринг-полным, если в нем присутствует команда условного перехода и команда логического сдвига.
Язык ассемблера x86 их содержит...
Причем тут предиктор ветвлений, как он может нарушить тьюринг-полноту? =)

 

Я, конечно, точно не знаю, но тут попахивает искуственным интелектом.
Ведь, по сути, машина юзает юзера, который генерит события и тем ,самым, условные переходы!

 

Предиктор переходов - это всего лишь внутренняя фича, с математической точки зрения совершенно прозрачная. (спроси leo, он тебе расскажет что там не то что искусственным, а иногда и никаким интеллектом не пахнет.) То же самое относится к кешу, TLB, Out-of-Ordering, superscalar и прочим потугам выжать побольше из одного гигагерца.
не одна из этих заморочек не меняет алгоритмы работы процессора, если он исправен, конечно. Но построить математическую модель неисправного процессора - вот достойная задача!

 

Согласен, что внутреняя фича, согласен, что статистика маленькая. Но это только пока... Но дело в том, что программер не может это программировать!
Процессор сам знает как ему лучше...

 

А программист знает, как сделать ему хуже
Машину Тьюринга не интересует ее внутренне устройство. У любого алгоритма есть вход и выход. И у процессора есть вход и выход. А что внутри - не имеет значения. Внутри Pentium4, Athlon64 и Core2 не имеют практически ничего общего, что не мешает им одинаково себя вести с алгоритмической точки зрения.

 

Насколько я знаю машина Тьюринга определяется своим внутренним устройством.

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

 

С точки зрения математики и машины Тьюринга, нет такого понятия как скорость выполнения элементарной операции. И способ выполнения элементароной операции тоже не важен. И даже то, что внутри операции выполняются не в том же порядке, в каком они идут в коде, тоже ни кого не волнует

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

 

АЛУ - это как раз то место, где они совсем не похожи...
Да и регистровые файлы у них шибко разные...

 

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

 

Встречный интересный вопрос - а что есть разум?
Не машина Тьюринга - это, например аналоговая ЭВМ. Не смейтесь, мы их в институте проходили. И даже лабы делали.

 

Точно не знаю, наверное- асоциативная память...?

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

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

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

 

ПЛИСы не являются машиной Тьюринга, но до интеллекта им явно далековато

 

ПЛИС - программируемая интегральная схема? А почему ты думаешь, что она не моделируется машиной Тьюринга?

 

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

 

Мм.. Про параллельность я не подумал. При желании, параллельность вносит недетерменизм, может это уже и за пределами машины Тьюринга. К сожалению, хреновый из меня математик, не знаю точного определения, только на уровне здравого смысла.