Cтраница 2
Преобразователь А называется преобразователем Черча - Россера, если для любого элемента и любой функции распределения памяти JA результат ЛРезУльтат ( d, л) состоит из одного элемента. [16]
Таким образом, свойство Черча - Россера означает единственность результата в интересующем нас смысле. [17]
Детерминированные преобразователи - преобразователи Черча - Россера, так как они всегда имеют единственный результат. [18]
Отношение выводимости в системах Черча - Россера обладает таким свойством, что элементарный переход от одного элемента к другому определяется лишь отношением выводимости и не определяется никаким управлением извне. Этот факт ограничивает область применения системы Черча - Россера. Более общей моделью служат преобразователи Черча - Россера - недетерминированные дискретные преобразователи, обладающие свойством функциональности отображения вход - результат. Преобразователи Черча - Россера - более удобное средство для задания вычислений по сравнению с системой Черча - Россера, так как такие преобразователи Позволяют за счет управления более гибко описывать процесс обработки. [19]
Преобразователь А называется преобразователем Черча - Россера относительно ( &, ( г), если для любого d 6 множество результатов A ( d, ( г) состоит из одного элемента. Поэтому можно сказать, что А - преобразователь Черча - Россера относительно (, ( г), если все реализации Л, начинающиеся в ситуации ( d, ( г), либо никогда не заканчиваются, либо всегда заканчиваются с одним и тем же результатом. [20]
Для решения задачи минимизации ЧПФ в системе Россера и Тьюкетта разработан метод [5], обобщающий описанный в § 1.2 метод на - пространство. [21]
Парксу, Давиду Поликански, Питу Римбею, Кэти Россер, Гаю Стилу, Ларри Теслеру, Филу Уадлеру, Робину Фрееману, Дану Фридману, Роберту Херма-ну, Рэю Химану и Джону Эллису за их резонанс со мной в критические минуты моей жизни; каждый по-своему, они помогли мне написать эту книгу. [22]
Необходимо отметить, что строгое определение системы Черча - Россера несколько отличается от приведенного здесь и охватывает более узкий класс систем. В некотором смысле для практических вычислений представляет интерес только система Черча - Россера, так как почти всегда требуется однозначность результата. [23]
Единственность нормальной формы выражения является следствием теоремы Черча - Россера. Сама теорема рассматривает последовательности редукций вообще и ни в коем случае не ограничивается р - и б-редукциями. [24]
Этот вывод следует из результатов, полученных Геделем, Россером, Черчем, Клини, Тьюрингом и Постом. [25]
Говорят, что отношение редукции является слабой редукцией Черча - Россера, если оно обладает слабым ромбическим свойством. Однако ни одна из константных функций, используемых нами, не нарушает ромбическое свойство. [26]
Мы говорим, что отношение редукции - - называется редукцией Черча - Россера, если отношение - - обладает ромбическим свойством, и доказательство, упомянутое выше, действительно демонстрирует, что р-редукция является редукцией Черча - Россера. [27]
Теорема 9.7. Для преобразователей над свободной группой существует эффективный алгоритм, который, имея на входе произвольные описания локально-конечного распознавателя и обобщенного свойства Черча - Россера, проверяет выполнимость этого свойства для заданного распознавателя. [28]
Куайн [1941] по поводу того обстоятельства, что в системе этой книги появляется парадокс Бурали-Форти ( хотя, невидимому, ие проходит парадокс Каитора), как это было обнаружено Россером и Лиидоиом ( Roger С. [29]
Мы говорим, что отношение редукции - - называется редукцией Черча - Россера, если отношение - - обладает ромбическим свойством, и доказательство, упомянутое выше, действительно демонстрирует, что р-редукция является редукцией Черча - Россера. [30]