Избранное
ЭБ Нефть
и Газ
Главная
Оглавление
Поиск +
Еще книги ...
Энциклопедия
Помощь
Для просмотра
необходимо:


Книга: Главная » Сборник N.N. Проблемы математической логики Сложность алгоритмов и классы вычислимых функций
 
djvu / html
 

НО X. Ямада
дает нам модель цифровой вычислительной машины, более реалистичную в частных аспектах.
Настоящая работа, которая является попыткой построить математическую модель для цифровых машин, касается класса многоленточных машин Тьюринга, которые с некоторыми ограничениями применяются для вычислений некоторого класса функций в реальное время. Употребляя цифровую вычислительную машину, важно знать время, необходимое для вычисления данной функции. Однако, как известно автору, не было попыток исследовать общую теорию такого рода1). В качестве начала в этом направлении автор исследовал вычисления в реальное время некоторых рекурсивных функций посредством подкласса машин Тьюринга. Эта работа не претендует на полноту, и необходимы дальнейшие исследования. Тем не менее результаты предыдущих исследований положены в основу этой статьи и сведены в разд 2. В качестве примера в разд. 3 рассмотрено построение некоторой машины из рассматриваемого класса для вычисления полиномов. Для детального рассмотрения интересующегося читателя отсылаем к первоисточнику [8]. В разд. 4 этой статьи мы даем дальнейшую разработку теории и устанавливаем основную теорему, согласно которой вне зависимости от правил вычисления существует подкласс рекурсивных функций, которые не могут быть вычислены в реальное время. Автор полагает, что читатель знаком с основами теории машин Тьюринга и рекурсивных функций [2, 3].
2. ВЫЧИСЛЕНИЯ В РЕАЛЬНОЕ ВРЕМЯ С ПОМОЩЬЮ НЕКОТОРОГО КЛАССА МАШИН ТЬЮРИНГА
В этом разделе приведены более ранние результаты, полученные автором [8].
Рассмотрим однозначную функцию/ одного переменного, которая всегда принимает целое значение j(x) для любого положительного целого значения аргумента х. (В настоящей работе мы ограничиваемся этим классом функций. Рассмотрение более общих классов функций — возможное направление будущих исследований.)
Определим бесконечное множество Л натуральных чисел
Л = {/М; xs=N, fU)>0}, (1)
где N — множество всех положительных целых чисел. Таким образом, А есть положительная область значений / при целом аргументе х. (Если f — рекурсивная функция, то А —рекурсивно
!) В годы, последующие за опубликованием данной статьи, появились работы, в которых исследовался вопрос о времени, необходимом для вычисления функций на машинах Тьюринга и других автоматах. — Прим. ред.

 

1 10 20 30 40 50 60 70 80 90 100 110 120 130 140 141 142 143 144 145 146 147 148 149 150 160 170 180 190 200 210 220 230 240 250 260 270 280 290 300 310 320 330 340 350 360 370 380 390 400 410 420 430


Математика