Математическая логика и теория алгоритмов

29. Построить машины Тьюринга Т\ и То, перерабатывающие любые числа и в О и и+1 соответственно, при условии, что числа запи­ саны только с использованием алфавита/;(={ 1}, т.е. п обозначено сло­ вом и = 111...1. /1+1 30. Составить команды машины Тьюринга, которая будет счи­ тать записанные подряд (без пропусков) палочки и запишет их число; 1) в двоичной системе счисления; 2) в троичной системе счисления; 3) в системе счисления с основанием п. 31. На ленте записано число в системе счисления с основанием п. Составить команды машины Тьюринга, которая запишет число: 1) непосредственно следующее за данным; 2) непосредственно предшествующее данному. 32. На ленте записано некоторое число слов Р\,Рг,...,Рк в алфа­ вите Л , разделенных звездочками (*, Составить команды маши­ ны Тьюринга, которая считала бы количество слов и записывала бы их число: 1) в алфавите { ! } ; 2) в двоичной системе счисления; 3) в троичной системе счисления; 4) в системе счисления с основанием п. 33. Построить машину Тьюринга, которая приписывала бы справа от любого слова Р в алфавите А слово ааЪ{а,Ъ&А). 34. Выяснить, в какое слово перерабатывается слово т * г ма­ шиной Тьюринга: gol'S'o^o q\*Rq\ qi*Lq2 qoSoRqi q\Solq2 q2SaRqo q\\Rq] q2^Lqi (начальной конфигурацией является конфигурация q o m * n ) . 35. Построить машину Тьюринга для умножения на 2. 272