Обсуждение:Машина Тьюринга
Проект «Информационные технологии» (уровень II, важность для проекта высшая)
Эта статья тематически связана с вики-проектом «Информационные технологии», цель которого — создание и улучшение статей по темам, связанным с информационными технологиями. Вы можете её отредактировать, а также присоединиться к проекту, принять участие в его обсуждении и поработать над требуемыми статьями. |
Об определении машины Тьюринга[править код]
Хорошо бы добавить формальное определение машины Тьюринга на языке только конечных слов.
Назначение раздела "Интуитивное понимание" не вполне понятно. Он не добавляет ничего нового к предыдущему. Лучше было бы проиллюстрировать изложение простым примером.
Algo 13:02, 26 сентября 2006 (UTC)
Совершенно не ясно для чего же все-таки нужна машина Тьюринга
Насколько я понял, машина Тьюринга - абстрактное понятие
- В целом да (поскольку длина ленты не ограничена), но есть пару реальных реализаций, пусть и больше для тренировки мозгов. --A.I. 15:02, 23 ноября 2006 (UTC)
В английском варианте статьи ( http://en.wikipedia.org/wiki/Turing_machine ) в принципе написано тоже самое, но там это как-то более структурировано. Кроме того там много иллюстраций :( + внушительный список литературы
- Никто не мешает Вам перевести английскую статью ;) --A.I. 02:43, 3 декабря 2006 (UTC)
Машина Тьюринга используется для сравнения алгоритмов по сложности--Rigid 10:30, 31 мая 2008 (UTC)
____________________________________________
Принципиальная ошибка: В статье написано
Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа в таблице соответствует правило,
тогда как на самом деле детерминированная машина - это у которой на каждую пару состояние-символ есть не больше одного правила, т.е. правило может быть одно, а может его и не быть вовсе. В доказательство могу привести хотя бы английскую википедию:
deterministic Turing machine (DTM) for which the action table has at most one entry for each combination of symbol and state.
Dartkam 08:35, 7 июня 2009 (UTC)
______________________________________________
Ошибка в примере "умножителя". Не хватает двух правил:
q81 -> q81L, q8= -> q8=L.
--Portnov 17:35, 23 декабря 2009 (UTC)
Пример машины Тьюринга[править код]
Набор правил дан, а состояния qi не описаны. [User:4st] 10:16 1.04.11 (UTC)
- Присоединяюсь. Также не описано, что такое звёздочка, крестик и R. Поэтому сложно проверить последние правки. --infovarius 07:41, 15 октября 2011 (UTC)
Терминология[править код]
Господа, всё-таки передвижение по ленте "влево или вправо" - не совсем правильный термин (допускает толкование передвижения по ширине ленты). Правильнее было бы, наверное, писать "вперёд и назад". Либо нужна иллюстрация. --maqs 14:17, 15 января 2010 (UTC)
Движение "влево и вправо" допускается, вот только при решении задач удобнее считать движущейся головку, а не ленту, поэтому движения г
оловки и ленты относительно друг друга противоположны. [User:4st] 10:12 1.04.11.
Приведение статьи к более структурированному и ясному виду[править код]
Хочу убрать текущий пример и привести более простые примеры с иллюстрациями, если нельзя, то могу в обсуждение запостить, а вы оцените стоит ли вносить в главную статью.
рекомендованная литература[править код]
Интересная статья спасибо. Ещё хотелось бы несколько рекомендаций на фундаментальные труды данной отрасли научного знания: искусственные формальные языки и основы алгоритмики (и основ программирования): исторический, философский и теоретический аспекты - кто этим хорошо занимался может порекомендуют литературу для разного уровня - от научно-популярных книг до сугубо специальных тем и мат.аппаратом с детальным разбором. Что-то типа Кнута и т.д. - пусть даже будут рекомендации на зарубежных (не переведённых) классиков. Вообщем что-то по типу further reading 178.66.198.142 22:01, 9 июня 2014 (UTC)
Правила перехода[править код]
"Для каждой возможной конфигурации <qi, aj> имеется ровно одно правило". Тогда как в приведённом примере некоторые клетки таблицы переходов пустые.85.140.206.60 09:17, 9 июня 2015 (UTC)
"Для каждой возможной конфигурации". Что значит для "каждой возможной"? Откуда мы знаем, какие конфигурации возможны, а какие нет? 85.140.206.60 09:19, 9 июня 2015 (UTC)
C-машина Тьюринга[править код]
[1] и работы Dina Goldin с сотоварищами намекают (они хорошо цитируются, так что не МАРГ), что уже у Тьюринга был упомянут вариант C-машины (choice machine) с открытой моделью вычислений (интерактивный ввод), в отличие от традиционных машин Тьюринга. И при этом на первый взгляд (а возможно и вообще) C-машины не сводимы к A-машинам, описываемым в данной статье. Этот факт было бы хорошо в статье упомянуть, так как обычный сегодня компьютер на практике С-машина. Весь сыр бор о том, что модель акторов и т. п. не сводится к машине Тьюринга (хотя бы из-за заложенного в модель акторов недетерминизма) и тем самым является более богатой моделью вычислений. РоманСузи 07:14, 19 ноября 2015 (UTC)
Не является ли сервер в сети интернет полной машиной Тьюринга?[править код]
Пишут, что количество данных на компьютере конечно, даже если вместо жёсткого диска будет черная дыра такого же размера. А лента бесконечная. Однако, трафик - тоже бесконечный. Если нужно, чтобы он был "детерминистичный" - то ещё проще. Машина получает содержимое файлов от разных клиентов и должна их зашифровать и отдать. Можно 0 и 1 отправлять. Так может сервера можно приравнять к полной машине Тьюринга?
— 178.169.86.119 02:30, 18 декабря 2020 (UTC) Михаил.
- Не является - МТ должна быть способна отредактировать любой элемент рабочей ленты со сколь угодно большими промежутками между таким редактированием и при этом иметь возможность узнать значения в любой ячейке ленты. Без бесконечной памяти такое не выйдет сделать. adamant.pwn — contrib/talk 07:52, 18 декабря 2020 (UTC)