Меню
Главная
Случайная статья
Настройки
|
Эта статья тематически связана с вики-проектом «Информационные технологии», цель которого — создание и улучшение статей по темам, связанным с информационными технологиями. Вы можете её отредактировать, а также присоединиться к проекту, принять участие в его обсуждении и поработать над требуемыми статьями.
Содержание
Об определении машины Тьюринга
Хорошо бы добавить формальное определение машины Тьюринга на языке только конечных слов.
Назначение раздела "Интуитивное понимание" не вполне понятно. Он не добавляет ничего нового к предыдущему. Лучше было бы проиллюстрировать изложение простым примером.
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)[ответить]
Правила перехода
"Для каждой возможной конфигурации имеется ровно одно правило". Тогда как в приведённом примере некоторые клетки таблицы переходов пустые.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)[ответить]
|
|