Re: Является ли современный многоядерный компьютер машиной Тьюринга?

А какая разница?

Re: Является ли современный многоядерный компьютер машиной Тьюринга?

А почему отвечать вопросом на вопрос такое УГ? Можно ж было просто ответить - я не вижу никакой разницы, поэтому современный компьютер == машина Тьюринга.

А насчет разницы, то вот цитата из Википедии:

Turing machines are not intended as a practical computing technology, but rather as a thought experiment representing a computing machine. They help computer scientists understand the limits of mechanical computation.

Re: Является ли современный многоядерный компьютер машиной Тьюринга?

По-моему, машина Тьюринга - это как цикл Карно в термодинамике.

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

Re: Является ли современный многоядерный компьютер машиной Тьюринга?

> А почему отвечать вопросом на вопрос такое УГ?
А почему ты решил, что отвечать вопросом на вопрос - такое УГ?

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

Re: Является ли современный многоядерный компьютер машиной Тьюринга?

Например, ликвидировать свою безграмотность ...

Re: Является ли современный многоядерный компьютер машиной Тьюринга?

Ни в коем разе. Машина Тьюринга по определению бесконечна, а комп - конечен. Вопрос некорректно поставлен. Машина Тьюринга - это модельное представление. Правильно было бы сказать, что поведение компа+определённого ПО может быть описано при помощи модельного представления Машины Тьюринга.

Re: Является ли современный многоядерный компьютер машиной Тьюринга?

> Например, ликвидировать свою безграмотность ...
В чём заключается безграмотность которую ты хочешь ликвидировать - ты не знаешь как работает современный компьютер или как работает машина тьюринга? Если первое - то просто не заморачивай себе голову машиной тьюринга, а читай про устройство нитересующей тебя машины, если второе, то займись чем-нибудь более интересным, ни разу не видел, что бы эта абстракция была бы кому-либо полезна.

Re: Является ли современный многоядерный компьютер машиной Тьюринга?

>>Машина Тьюринга по определению бесконечна
По-моему, не только это. Мне кажется, что есть ещё одна фича, которая делает современный комп существенно быстрее, чем машина Тьюринга, будь она реализована в железе ...

>>Вопрос некорректно поставлен. Машина Тьюринга - это модельное представление.
Возможно. Просто есть же описание машины Тьюринга (например, вот здесь -  http://en.wikipedia.org/wiki/Turing_machine), так вот если его реализовать как реальную машину - будет ли оно быстрее или медленнее современных машин?

Это, наверное, похоже на цикл Карно - т.е. чтоб его реализовать, поршни там должны будут перемещаться с бесконечно медленной скоростью.

Re: Является ли современный многоядерный компьютер машиной Тьюринга?

> Просто есть же описание машины Тьюринга (например, вот здесь -  http://en.wikipedia.org/wiki/Turing_machine), так вот если его реализовать как реальную машину - будет ли оно быстрее или медленнее современных машин?
ахаха смотря на каких задачах. А так, не очень давно здесь была ссылка на реализацию оной, из рулона туалетной бумаги и самописца. Вряд ли она будет быстрее.

Re: Является ли современный многоядерный компьютер машиной Тьюринга?

>>Машина Тьюринга по определению бесконечна
>По-моему, не только это. Мне кажется, что есть ещё одна фича, которая делает современный комп существенно быстрее, чем машина Тьюринга, будь она реализована в железе ...
Машина Тюринга не динамическая система, поэтому мы не можем сказать что она будет медленней компьютера. В простейшем случае, это что то вроде функции: мы даём ей аргумент, назад получаем значение. Если это происходит мгновенно, она быстрее любого компьютера. Если же мы её эмулируем при помощи компьютера, то она всегда медленней. Потому что, компьютер это и есть машина Тюринга (компьютер можно разобрать на конечную информацию, состоящую из 1/0 и всего два бинарных оператора) То есть получается машина Тюринга внутри машины Тюринга. Быстрее она от этого не станет.

Re: Является ли современный многоядерный компьютер машиной Тьюринга?

> Является ли современный многоядерный компьютер машиной Тьюринга?
> Или напротив идеализированная модель Тьюринга помогает нам понять, как работают современный компьютеры?
Если убрать "напротив" то ответ "Да" :). Вот очень извесный пример:

 http://en.wikipedia.org/wiki/Halting_problem

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

Re: Является ли современный многоядерный компьютер машиной Тьюринга?

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

Re: Является ли современный многоядерный компьютер машиной Тьюринга?

Ну, так и есть. По-моему, фишка в том, что машина Тьюринга - это простейшая машина, на которой можно считать. Ну, и одна из реализаций (busy beaver) ограничивается тремя состояниями. А современный комп гораздо сложнее (и потому быстрее), хотя и не мощнее в смысле вычислительных возможностей. Как минимум, он не последовательный, а random access, т.е. позволяет операции с указателями (поэтому эти операции и не любят любители верификации, поскольку они значительно усложняют тьюрингову модель). Т.е. на современном компе можно посчитать то же самое, что и на Тьюринговой машине, но получится это гораздо быстрее (поскольку бесконечный цикл для машины Тьюринга - не проблема).

Это всё в той же статье в википедии про машину Тьюринга написано:

A limitation of Turing Machines is that they do not model the strengths of a particular arrangement well. For instance, modern stored-program computers are actually instances of a more specific form of abstract machine known as the random access stored program machine or RASP machine model. Like the Universal Turing machine the RASP stores its "program" in "memory" external to its finite-state machine's "instructions". Unlike the Universal Turing Machine, the RASP has an infinite number of distinguishable, numbered but unbounded "registers"—memory "cells" that can contain any integer (cf Elgot and Robinson (1964), Hartmanis (1971), and in particular Cook-Rechow (1973); references at random access machine). The RASP's finite-state machine is equipped with the capability for indirect addressing (e.g. the contents of one register can be used as an address to specify another register); thus the RASP's "program" can address any register in the register-sequence. The upshot of this distinction is that there are computational optimizations that can be performed based on the memory indices, which are not possible in a general Turing Machine; thus when Turing Machines are used as the basis for bounding running times, a 'false lower bound' can be proven on certain algorithms' running times (due to the false simplifying assumption of a Turing Machine). An example of this is binary search, an algorithm that can be shown to perform more quickly when using the RASP model of computation rather than the Turing machine model.