Вопросы, связанные с теорией вычислимости, ака теорией рекурсии
Я не понимаю, почему проблема остановки так часто используется, чтобы исключить возможность определения, останавливается ли программа. Википедия [статья] [1] правильно объясняет, что детерминированная машина с конечной памятью либо остановит, либо повторит предыдущее состояние. Вы можете...
Нам дали следующее упражнение. Позволять f(n)={100n occurs in the decimal representation of πelsef(n)={10n occurs in the decimal representation of π0else\qquad \displaystyle f(n) = \begin{cases} 1 & 0^n \text{ occurs in the decimal representation of } \pi \\ 0 & \text{else}\end{cases} Докажите, что...
Мы знаем, что проблема остановки (на машинах Тьюринга) неразрешима для машин Тьюринга. Проводятся ли некоторые исследования того, насколько хорошо человеческий разум может справиться с этой проблемой, возможно, с помощью машин Тьюринга или компьютеров общего назначения? Примечание : Очевидно, что в...
Существует ли набор конструкций языка программирования на языке программирования, чтобы его можно было считать завершенным по Тьюрингу? Из того, что я могу сказать из Википедии , язык должен поддерживать рекурсию или, по-видимому, должен иметь возможность работать без остановки. Это все, что...
Сопоставление паттернов высокого порядка - неразрешимая проблема. Это означает, что не существует алгоритма, который, учитывая уравнение a => b, где aи bявляются открытыми слагаемыми в простом типе лямбда-исчисления, находит замену так S, что aS => bS, где =>означает «имеет такую же Bn...
Я столкнулся со странной проблемой при написании интерпретатора, который (должен) подключаться к внешним программам / функциям: функции в «C» и «C ++» не могут перехватывать переменные функции , например, я не могу создать функцию, которая вызывает «printf» с точно такими же аргументами, которые он...
Я видел повсюду переполнение стека, например, здесь , здесь , здесь , здесь , здесь и некоторые другие, которые я не хочу упоминать, что «любая программа, использующая рекурсию, может быть преобразована в программу, использующую только итерацию». Была даже тема с сильным голосованием и ответом с...
В этом ответе упоминается Обычный язык может быть распознан конечным автоматом. Для контекстно-свободного языка требуется стек, а для контекстно-зависимого языка требуются два стека (что эквивалентно тому, что для него требуется полная машина Тьюринга) . Я хотел знать относительно правды смелой...
В теории вычислимости и сложности (и, возможно, в других областях) сокращения являются повсеместными. Существует много видов, но принцип остается тем же: показать, что одна проблема L1L1L_1 , по крайней мере, так же трудна, как и другая проблема L2L2L_2 путем сопоставления экземпляров из с...
Я пытался объяснить кому-то, что C завершена по Тьюрингу, и понял, что на самом деле не знаю, действительно ли он технически завершен по Тьюрингу. (C как в абстрактной семантике, а не как в реальной реализации.) «Очевидный» ответ (грубо говоря: он может адресовать произвольный объем памяти, поэтому...
Существуют ли теоретические машины, которые превосходят возможности машин Тьюринга хотя бы в некоторых
Реферат: Согласно теореме Райс, все невозможно. И все же, я делаю это якобы невозможное постоянно! Конечно, теорема Райс не просто говорит, что «все невозможно». В нем говорится что-то более конкретное: «Каждое свойство компьютерной программы не вычислимо». (Если вы хотите разделить волосы, каждое...
Я знаю, что у Идриса есть зависимые типы, но он не завершен. Что он не может сделать, отказавшись от полноты Тьюринга, и связано ли это с наличием зависимых типов? Я предполагаю, что это довольно специфический вопрос, но я не знаю много о зависимых типах и связанных системах...
Видя, что в иерархии Хомского языки типа 3 могут распознаваться конечным автоматом без внешней памяти (т. Е. Конечным автоматом), тип 2 - конечным автоматом с одним стеком (т. Е. Автоматом с понижением) и тип 0 - конечный автомат с двумя стеками (или, что эквивалентно, лента, как в случае с...
Эта 579-битная программа в двоичном лямбда-исчислении имеет неизвестный статус остановки: 01001001000100010001000101100111101111001110010101000001110011101000000111001110 10010000011100111010000001110011101000000111001110100000000111000011100111110100...
Я планирую провести зимний курс по разному количеству тем, одной из которых будут составители. Теперь я столкнулся с этой проблемой, думая о заданиях, которые нужно давать на протяжении всего квартала, но это поставило меня в тупик, поэтому я мог бы вместо этого использовать его в качестве примера....
Существуют ли полные лямбда-исчисления по Тьюрингу? Если да, то каковы несколько
Мне интересно, есть ли хороший пример для простой для понимания проблемы NP-Hard, которая не является NP-Complete и не неразрешима? Например, проблема остановки - NP-Hard, а не NP-Complete, но неразрешима. Я считаю, что это означает, что это проблема, решение которой можно проверить, но не за...
Я проходил дискуссию по вопросу, как определить квантовые машины Тьюринга? и я чувствую, что квантовая ТМ и недетерминированная ТМ - это одно и то же. Ответы на другой вопрос не касаются этого. Являются ли эти две модели одинаковыми? Если нет, Каковы различия между квантовой ТМ и НДТМ? Существуют...
Теорема Райса говорит нам, что единственные семантические свойства машин Тьюринга (т.е. свойства функции, вычисляемой машиной), которые мы можем решить, - это два тривиальных свойства (то есть всегда истинно и всегда ложно). Но есть и другие свойства машин Тьюринга, которые нельзя решить. Например,...