Я нашел следующее объяснение от Math exchange Язык является распознаваемым тогда и только тогда, когда существует машина Тьюринга, которая остановится и примет только строки на этом языке, а для строк не на этом языке ТМ либо отклонит, либо не...

Я новичок в Agda, и мне нужна помощь, чтобы понять функцию Decidable и тип Dec . Я пытаюсь определить предикат логики первого порядка и хочу закодировать с доказательством какое-то логическое значение. Я нашел способ сделать это с помощью типа...

Я знаю, что этот вопрос задавался ранее, но, честно говоря, я не совсем понимаю его. В настоящее время я изучаю теорию вычислений и подхожу к термину «Докажите, что язык разрешимый, узнаваемый или регулярный». Проще говоря, что они на самом деле...

Рассмотрим язык $E_{tm}={ \langle M \rangle: M\text{является машиной Тьюринга, которая ничего не принимает }$ Я не уверен, как даже начать. Моя идея состоит в том, чтобы обеспечить сокращение времени полигонов из некоторой задачи NP - Complete....

Я читал в книге (Hromkovic, Communication Complexity and Parallel Computing), что существует бесконечное количество нерекурсивно-перечислимых (не-RE) языков, которые состоят только из 1 элемента? Но возможно ли это? Я думал, что для того, чтобы язык...

Ниже у меня есть ванильный индуктивный тип данных для некоторых формул, и мне интересно, есть ли способ оптимизировать этот процесс для определения решаемого равенства по любому индуктивно определенному типу внутри Agda (то есть без использования...