Вычислимые функции. 3 страница(n массивов единиц, n ≥ 1), где l - фиксировано, n - произвольное.
Вариант 10 1. Построить в алфавите машину Тьюринга, обладающую следующими свойством (предполагается, что в начальный момент головка обозревает самый левый символ слова, и в качестве пустого символа берется 0): § машина имеет пять команд, применима к словам и не применима к словам . 2. По словесному описанию машины Тьюринга построить ее программу (в алфавите § При заданном головка машины, двигаясь вправо от какой- либо пустой ячейки, находит первый при таком перемещении массив, содержащий не менее единиц, стирает в нем первые единиц и останавливается на самой правой из ячеек, в которых были стертые единицы. Остальное содержимое ленты не меняется. 3. По операторной схеме алгоритма ₤ и описанию машин, входящих в нее, построить программу машины Т, задаваемой этой схемой, и найти результат применения машины Т к слову Р: ₤
(начальные состояния машин а заключительные — ). 4. Построить машину Тьюринга, правильно вычисляющую функцию : 5. Построить машину Тьюринга, преобразующую один машинный код в другой. Заданный l -кратный код набора преобразуется в решетчатый код (l - фиксированное, меняется α, ).
Вариант 11 1. Построить в алфавите машину Тьюринга, обладающую следующими свойством (предполагается, что в начальный момент головка обозревает самый левый символ слова, и в качестве пустого символа берется 0): § машина применима к словам , где , и не применима к словам , где . 2. Построить композицию машин Тьюринга по паре состояний и найти результат применения композиции к слову Р ( —заключительное состояние машины ):
3. Построить машину Тьюринга, вычисляющую функцию : 4. По программе машины Тьюринга Т записать аналитическое выражение для функций и , вычисляемых машиной Т (в качестве начального состояния берется , а в качестве заключительного — ):
T:
5. Построить машину Тьюринга, преобразующую один машинный код в другой. Решетчатый код с заданной совокупностью слов, расположенных на соответствующих решетках (1-й, 2-й и т.д.), преобразуется в l -кратный код с указанным значением l:
Вариант 12 1. По заданной машине Тьюринга Т и начальной конфигурации К1 найти заключительную конфигурацию ( — заключительное состояние): a) б) 2. Построить композицию машин Тьюринга по паре состояний и найти результат применения композиции к слову Р ( —заключительное состояние машины ):
3. Построить машину Тьюринга, вычисляющую функцию : 4. По программе машины Тьюринга Т записать аналитическое выражение для функций и , вычисляемых машиной Т (в качестве начального состояния берется , а в качестве заключительного — ):
T:
5. Построить машину Тьюринга, преобразующую один машинный код в другой. Решетчатый код с заданной совокупностью слов, расположенных на соответствующих решетках (1-й, 2-й и т.д.), преобразуется в l -кратный код с указанным значением l:
Вариант 13 1. По заданной машине Тьюринга Т и начальной конфигурации К1 найти заключительную конфигурацию ( — заключительное состояние): a) б) 2. Построить композицию машин Тьюринга по паре состояний и найти результат применения композиции к слову Р ( —заключительное состояние машины ):
3. Построить машину Тьюринга, вычисляющую функцию : 4. По программе машины Тьюринга Т записать аналитическое выражение для функций и , вычисляемых машиной Т (в качестве начального состояния берется , а в качестве заключительного — ):
T:
5. Построить машину Тьюринга, преобразующую один машинный код в другой. Решетчатый код с заданной совокупностью слов, расположенных на соответствующих решетках (1-й, 2-й и т.д.), преобразуется в l -кратный код с указанным значением l:
Вариант 14 1. По заданной машине Тьюринга Т и начальной конфигурации К1 найти заключительную конфигурацию ( — заключительное состояние): a) б) 2. Построить композицию машин Тьюринга по паре состояний и найти результат применения композиции к слову Р ( —заключительное состояние машины ):
3. Построить машину Тьюринга, вычисляющую функцию : 4. По программе машины Тьюринга Т записать аналитическое выражение для функций и , вычисляемых машиной Т (в качестве начального состояния берется , а в качестве заключительного — ):
T:
5. Построить машину Тьюринга, преобразующую один машинный код в другой. Заданный l -кратный код набора преобразуется в решетчатый код (функционирование машины не должно зависеть от значения l).
Вариант 15 1. По заданной машине Тьюринга Т и начальной конфигурации К1 найти заключительную конфигурацию ( — заключительное состояние): a) б) 2. Найти результат применения итерации машины Т по паре состояний ( , ) к слову Р (заключительными состояниями являются и ):
i=1, T:
3. Построить машину Тьюринга, вычисляющую функцию : 4. По программе машины Тьюринга Т записать аналитическое выражение для функций и , вычисляемых машиной Т (в качестве начального состояния берется , а в качестве заключительного — ):
|