Хотя общий случай неразрешим, многие люди все же решают задачи, достаточно хорошо эквивалентные для повседневного использования. В докторской диссертации Коэна о компьютерных вирусах он показал, что поиск вирусов эквивалентен проблеме остановки, но...

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

Класс вычислимости, который я беру, объясняет несколько языков, которые находятся в RE - REC (рекурсивно перечисляемые, но не рекурсивные, т.е. решаемые безостановочной машиной Тьюринга). Сначала показано, как один из них (L_d, язык машин Тьюринга,...

В качестве домашнего задания мне дали следующую грамматику: S: D D: AbBb | BaAb A: ε B: ε Я вычислил это с помощью LL (1) просто отлично. Первые наборы были: S: a, b D: a,b A: ε B: ε Были следующие наборы: S: $ D: $ A: b B:...