1
голосов
2ответов
3021 просмотров

How can I simulate a turing machine?

I don't quite understand the whole idea of a turing machine thing. I am currently tasked with making a busy beaver turing machine. But the thing I don't really get is it simulates input. So what kind of input do I simulate? For example, it's asking me how many 1s the 3 states busy beaver machine...

5
голосов
2ответов
916 просмотров

Can a language be Turing-complete without any support for arrays?

If a language has control structures and variables, but no support for arrays, lists, memory access and allocation, etc, can it be Turing-complete? Maybe if there was no limit to the amount of variables you can create, you can simulate arrays by creating variables like array_1, array_2, ... arra...

5
голосов
5ответов
1859 просмотров

What can awk do that sed can't?

I used sed for a batch ptovess where I could not do it with awk. Vould awk have done it? Or is it more a matter of choice and call awk and sed equivalent for the usage. They both do the common search replace similar with i/o. Is there a good example what can't be done with one that the other can?

30
голосов
11ответов
6887 просмотров

Создание кратчайшего полного по Тьюрингу интерпретатора

Я только что попытался создать интерпретатор языка как можно меньшего размера. Хотите присоединиться и попробовать? Правила игры: Вам следует указать интерпретируемый язык программирования. Если это язык, который вы изобрели, он должен сопровождаться списком команд в комментариях. Ваш...

10
голосов
10ответов
2950 просмотров

Может ли язык быть полным по Тьюрингу, но неполным в других отношениях?

Например, есть ли определенные вещи при написании операционной системы, которые нельзя реализовать на полном языке Тьюринга?

1
голосов
2ответов
281 просмотров

Какие изящные и завершенные по Тьюрингу машины * вы знаете? Есть ли один из Книги?

Лямбда-исчисление, конечно, довольно элегантно, но вас не беспокоит асимметрия между вводом и выводом функции? Т.е. вы можете заставить функцию принимать два параметра (возвращая функцию), но вы не можете заставить ее возвращать два значения. Я не думаю, что мы могли бы найти его в Книге .

14
голосов
3ответов
1749 просмотров

Остановка на неполных по Тьюрингу языках

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

46
голосов
13ответов
10109 просмотров

Каковы практические рекомендации по оценке «полноты по Тьюрингу»?

Я прочитал "what-is-turing-complete" и страницу в Википедии. , но меня меньше интересуют формальные доказательства, чем практические последствия полноты по Тьюрингу. На самом деле я пытаюсь решить, можно ли использовать только что созданный игрушечный язык в качестве языка общего назначения...

55
голосов
5ответов
18559 просмотров

Почему «Игру жизни» Конвея можно назвать универсальной машиной?

Недавно я читал об искусственной жизни и наткнулся на утверждение: "Игра Конвея of Life достаточно сложен, чтобы его можно было классифицировать как универсальную машину ». У меня было лишь приблизительное представление о том, что такое универсальная машина есть, и Википедия приблизила меня ...

45
голосов
8ответов
13734 просмотров

Практические неполные по Тьюрингу языки?

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

10
голосов
4ответов
1287 просмотров

Полны ли деревья выражений LINQ по Тьюрингу?

Как они есть в .Net 3.5. Я знаю, что они в 4.0, так как DLR работает с ними, но меня интересует версия, которая есть у нас сейчас.

111
голосов
15ответов
35783 просмотров

Шаблоны C ++ по Тьюрингу?

Мне сказали, что система шаблонов в C ++ является полной по Тьюрингу во время компиляции. Это упоминается в этом сообщении , а также в wikipedia . Можете ли вы привести нетривиальный пример вычисления, использующего это свойство? Полезен ли этот факт на практике?

499
голосов
14ответов
176210 просмотров

Что такое полный Тьюринга?

Что означает выражение «Полный Тьюринга»? Можете ли вы дать простое объяснение, не вдаваясь в слишком много теоретических деталей?