22
ответа
Когда теоретическая информатика полезна?
В классе мы узнали о проблеме остановки, Машинах Тьюринга, сокращениях, и т.д. Много одноклассников говорит, что это все абстрактные и бесполезные понятия, и нет никакого основного назначения в знании их (...
вопрос задан: 29 December 2016 21:39
12
ответов
Гольф кода машины Тьюринга
Хорошо парни, сегодняшняя цель состоит в том, чтобы создать средство моделирования Машины Тьюринга. Для тех, которые не знают, каково это, см. статью Wikipedia. Таблица состояния, которую мы используем сегодня, найдена в конце Формального...
вопрос задан: 27 November 2009 02:50
11
ответов
Когда Вы натолкнулись на проблему остановки в поле? [закрытый]
Когда Вы когда-либо лично наталкивались на проблему остановки в поле? Это может быть, когда коллега / босс предложил решение, которое нарушит фундаментальные пределы вычисления, или когда...
вопрос задан: 6 November 2018 15:38
9
ответов
Что такое Машина Тьюринга?
Что такое Машина Тьюринга и почему люди продолжают упоминать это? Мой IBM PC - все, что я должен сделать свое вычисление! Почему кто-либо заботится об этих машинах?
вопрос задан: 4 March 2013 04:52
9
ответов
[Закрываются] несколько уровней бесконечности
Некоторые программисты не видят много уместности в теоретических классах CS (особенно мои студенты). Вот что-то, что я нахожу очень релевантными. Позвольте мне создать его в частях для тех, которые не видели его прежде....
вопрос задан: 16 June 2009 16:49
6
ответов
Что такое полный Тьюринг?
Что означает выражение «полный Тьюринг»? Можете ли вы дать простое объяснение, не вдаваясь в слишком много теоретических деталей?
вопрос задан: 23 June 2012 00:22
6
ответов
Проблемы с универсальной машиной Тьюринга
Если у меня есть машина, назовите ее машиной 1, который может решить проблему: это - просто машина, не по сути Машина Тьюринга. Это может решить одну определенную проблему. Если эта точно та же самая проблема может быть решена...
вопрос задан: 3 April 2010 12:59
5
ответов
Машина Тьюринга по сравнению с машиной Von Neuman
Фон Архитектура фон Неймана описывает компьютер сохраненной программы, где инструкции и данные хранятся в памяти и работах машины путем изменения ее внутреннего состояния, т.е. инструкции...
вопрос задан: 26 December 2016 03:25
4
ответа
Что будет эквивалентно языку ассемблера операций над будет ли оригинальная машина Тьюринга?
Если исходное определение машины Тьюринга принять следующим образом: ... бесконечный объем памяти, полученный в виде бесконечной ленты, размеченной в квадраты, на каждом из которых символ ...
вопрос задан: 14 April 2015 03:43
4
ответа
Как делает не детерминированную работу машины Тьюринга?
Я понимаю, что они не реальны, и они, кажется, переходят вычисление каждый раз, когда существует 2 опции, вместо того, чтобы выбрать ту. Но, например, если я говорю это: "Не детерминировано предполагают взаимно однозначное соответствие p...
вопрос задан: 25 January 2010 14:35
3
ответа
иерархия chomsky и языки программирования
Я пытаюсь изучить некоторые аспекты Иерархии Chomsky, которые связаны с языками программирования, и я все еще должен прочитать Книгу Дракона. Я считал, что может быть проанализировано большинство языков программирования...
вопрос задан: 26 May 2015 09:49
3
ответа
Реализация управляющих структур в Brainfuck
Для непосвященных Brainfuck является языком, полным по Тьюрингу и имеющим только 8 команд, все из которых имеют буквальные эквиваленты в C: BF C
----------------------
> ++ ptr;
<--ptr;
+ ++ * ...
вопрос задан: 29 January 2013 19:35
2
ответа
Как Иерархия Chomsky и Машины Тьюринга должны влиять на дизайн языка?
Я в настоящее время учусь для теста дискретной математики, в котором мы изучаем иерархию Chomsky, и тип автоматизирует, которые распознают каждый уровень иерархии. Мне преподают что большинство...
вопрос задан: 26 May 2015 10:35
2
ответа
Ищу языки, не являющиеся полными по Тьюрингу
Я немного знаю о том, что такое машина Тьюринга и полный по Тьюрингу язык, но, чтобы лучше понять, может ли кто-нибудь привести примеры языков что не является полным по Тьюрингу? (может быть, даже машины ...
вопрос задан: 14 April 2015 06:33
2
ответа
Существует ли термин для конечного автомата, который, как гарантируют, остановится?
У меня была дискуссия ранее о конечном автомате, и был вопрос относительно того, не мог ли он остановиться на некотором входе. Это походит на свойство конечных автоматов, которое важно и...
вопрос задан: 24 June 2010 19:02
2
ответа
Каковы полезные пределы Линейных Ограниченных Автоматов по сравнению с Машинами Тьюринга?
Существуют языки, что Машина Тьюринга может обработать это, LBA не может, но быть там какими-либо полезными, практическими проблемами, которые не может решить LBAs, но ТМ могут? LBA является просто Машина Тьюринга с конечным...
вопрос задан: 24 February 2010 16:51
1
ответ
Таблица инструкции по машине Тьюринга
В определениях Машины Тьюринга говорится, что запрещается для одного читать/изменять, это - таблица инструкции (программа). Точно, Машина Тьюринга не имеет никакого доступа к своей собственной программе. Каковы преимущества могут быть...
вопрос задан: 8 October 2009 04:29
0
ответов
Машина Тьюринга - это реальное устройство или воображаемое понятие?
Когда я изучал машины и КПК Тьюринга, я думал, что первым вычислительным устройством была машина Тьюринга. Следовательно, я думал, что существует практическая машина под названием Turing ...
вопрос задан: 19 April 2019 20:04
0
ответов
Обычные ли .NET Выражения Turing complete?
Регулярные выражения часто называют классическим примером языка, который не завершен по Тьюрингу. Например, "регулярные выражения" даются в качестве ответа на этот вопрос SO, глядя ...
вопрос задан: 23 May 2017 11:45
0
ответов
Может ли гиперграф представлять недетерминированную машину Тьюринга?
Кто-нибудь знает какие-либо статьи, тексты или другие документы, в которых обсуждается использование гиперграфа для реализации или представления недетерминированной машины Тьюринга? Действительно ли они эквивалентны? Я уверен ...
вопрос задан: 13 April 2017 12:57
0
ответов
Разница между разрешимостью по Тьюрингу и разрешимостью совместно по Тьюрингу
Я действительно изо всех сил пытаюсь понять разницу между этими двумя. Из моего учебника это различие, по сути, описывает разницу, говоря, что язык является совместно узнаваемым, если он...
вопрос задан: 20 March 2017 09:39
0
ответов
Доказать, что этот язык неразрешимый
Неразрешима ли следующий язык L? L = {M | M - это описание машины Тьюринга, и существует вход x длины k такой, что M останавливается не более чем через k шагов} Я думаю, что это так, но я не мог ...
вопрос задан: 4 June 2015 04:29
0
ответов
Полнота по Тьюрингу лямбда-исчисления?
Как вы аргументируете тот факт, что лямбда-исчисление является полным по Тьюрингу (самым простым способом)?
вопрос задан: 8 December 2013 19:14
0
ответов
JAX-WS и Joda-Time?
Как мне написать сервис JAX-WS, чтобы @WebParam моего @WebMethod был Joda -Time класс, как DateTime? Будет ли работать @XmlTypeAdapter для параметра? Я развертываю GlassFish 2.1. Позвольте мне прояснить ...
вопрос задан: 17 August 2013 01:39
0
ответов
Постройте машину Тьюринга, чтобы решить, что ww ^ Rw
w ^ R является обратным w, а w равно {0, 1} *. Таким образом, TM должен выбрать слово, за которым следует обратная сторона этого слова, за которым следует слово.
Мне не нужен ответ, я просто хочу, чтобы зацепка началась и чтобы получить ...
вопрос задан: 29 June 2012 07:39
0
ответов
Какие все известные языки не могут быть восприняты машинами Тьюринга?
Например, язык машин Тьюринга, которые не принимают собственную кодировку, не может быть принят ни одной машиной Тьюринга.
вопрос задан: 26 June 2012 23:37
0
ответов
Есть ли у машины Тьюринга понятие «время»?
Будучи студентом, я изучал основы теории машин Тьюринга. Я никогда не видел никаких упоминаний об обработке по времени Тьюринга. Пример: машина Тьюринга, которая подсчитывает количество секунд, прошедших с момента...
вопрос задан: 22 June 2012 22:57
0
ответов
Как определить, является ли язык рекурсивным или рекурсивно перечисляемым?
Я должен определить, является ли язык (например, L = {a ^ nb ^ mc ^ s | 0 <= n <= m <= s}) регулярным, контекстно-независимым, рекурсивным, рекурсивно перечислимым или ни одного из них. Я знаю, как определить ...
вопрос задан: 16 February 2011 17:58
0
ответов
Как определить, является ли машина эквивалентом машины Тьюринга
Я нашел статью в Википедии со списком эквивалентов машины Тьюринга. Однако в нем не говорится о методе определения того, является ли данная машина эквивалентом машины Тьюринга. Нужно ли мне использовать ...
вопрос задан: 10 January 2011 09:18
0
ответов
Является ли PI вычислимым числом Тьюринга? [closed]
AFAIK, вычислимые числа Тьюринга - это числа, i-й индекс которых может быть возвращен машиной Тьюринга. Таким образом, невычислимое число будет чем-то вроде числа, десятичная дробь которого определяется, если какой-то ...
вопрос задан: 9 November 2010 13:43