Структуры данных и модели вычислений

         

Вычисление числовых функций


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

Значения функции и ее аргументов будем записывать в бинарном, унарном или каком-либо ином коде, для чего нам потребуется, соответственно, алфавит , и т.д. Значения аргументов перед вычислением должны быть представлены на ленте в виде псевдослова

где — код -го аргумента .

После вычисления содержимое ленты должно иметь вид

где — код значения функции при заданных значениях аргумента.

Упражнения

  1. Составить программу, перерабатывающую псевдослово

    в псевдослово , где — бинарный, а — унарный код некоторого числа из .

  2. Составить программу сложения и умножения чисел в унарном и бинарном кодах.
  3. Составить программу для удвоения числа в бинарном и унарном кодах.
  4. Составить программу деления нацело натуральных чисел в унарном коде.



Содержание  Назад  Вперед