Структуры данных и модели вычислений
Вычисление числовых функций
Чтобы вычислять значения числовых функций с помощью тьюринговых программ, необходимо выбрать способ кодирования на ленте аргументов и значений функции. Мы рассматриваем функции из в , где — множество натуральных чисел, включая , а .
Значения функции и ее аргументов будем записывать в бинарном, унарном или каком-либо ином коде, для чего нам потребуется, соответственно, алфавит , и т.д. Значения аргументов перед вычислением должны быть представлены на ленте в виде псевдослова
где — код -го аргумента .
После вычисления содержимое ленты должно иметь вид
где — код значения функции при заданных значениях аргумента.
Упражнения
- Составить программу, перерабатывающую псевдослово
в псевдослово , где — бинарный, а — унарный код некоторого числа из .
- Составить программу сложения и умножения чисел в унарном и бинарном кодах.
- Составить программу для удвоения числа в бинарном и унарном кодах.
- Составить программу деления нацело натуральных чисел в унарном коде.
