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

181 а ). Показать , что схема        → •→ → ∗→∗ = α Λ α α α 1 1 1 11 F определяет нормальный алгоритм F над алфавитом В , применимый только к тем словам в алфавите В , которые являются цифрами , и такой , что ( ) 0 nF = для любого п . б ) Показать , что нормальный алгоритм G над алфавитом В , определяемый схемой      → •→ ∗→∗ = α Λ α ,11 1 G применим только к тем словам в алфавите В , которые суть цифры , причем ( ) 1n nG += для любого п . в ). Построить схему нормального алгоритма в алфавите В , перерабатывающего ( ) 2 1 n,n в ( ) 2 1 n n − . г ). Построить нормальный алгоритм умножения на 2 . 14. Построить нормальный алгоритм над алфавитом В = { 1, ∗} для арифметических операций сложения и вычитания . 15. Построить нормальный алгоритм для умножения на фиксированное число п . 16. Пусть А = { 1, ∗ , а ,b } . Показать , что следующий нормальный алгоритм b1 → 1b ∗ 1 →∗ а 1 → 1b а ∗→Λ а →Λ b → 1 1 ∗→∗ а производит умножение двух чисел n и m , записанных в алфавите В = { l, ∗} в виде одного слова m n 1... 111 1... 111 ∗ . 17. Построить нормальный алгоритм F над алфавитом А такой , что для любого слова Р в А было F( Р )= РР . 18. Построить нормальный алгоритм для получения целой части при делении : а ) на 3 ; б ) на п . 19. Построить схему нормального алгоритма , равного композиции нормальных алгоритмов F и G в алфавите А = { 1, ∗} :