Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

10. Пусть Ki исчисление предикатов первого порядка. Указать, какое из сле­ дующих утверждений истинно: 1) теория Ki непротиворечива, неполна в широком смысле и является разрешимой теорией; 2) теория Ki непротиворечива, полна в узком смысле и является разре­ шимой теорией; 3) теория Ki непротиворечива, полна в широком и узком смыслах и, кро­ ме того, Ki - разрешимая теория; 4) теория Ki противоречива, полна в широком смысле и является разре­ шимой теорией; 5) теория Ki непротиворечива, полна в широком смысле, не полна в уз­ ком смысле и является неразрешимой теорией. Тест по теории алгоритмов (тест Ж» 5) 1. Результат применения нормального алгоритма аЬ ^ с < bb ксшъу P=abcbad^2i^Qw. сс ^ b 1) da 2) dad 3) dd 4) cccd 5) ab 2. Результат применения нормального алгоритма аЬ ^ d < be •а кс л о в у р а в е н : dd —^ b 1) dad 2) da 3) dd 4) ccd 5) aa 3. Результат применения машины Тьюринга Tf. qoo so до qosorqo qob So qi qisorqi qic с q2 к слову P= abcc равен (в начальный момент читаюш,ая головка машины обозре­ вает первую букву слова Р)\ 1) abc 2) cc 3) be 4) ab 5) bcc 4. Результат применения машины Тьюринга Ti (см. предыдуш,ую задачу) к слову/*= аЬс равен (в начальный момент читаюш,ая головка машины обозре­ вает первую букву слова Р) 1) abc 2) ab 3) be 4) с 5) b 5. Для каждого нормального алгоритма суш,ествует вполне эквивалентный ему 253