Cтраница 3
Часто при введении понятия интуитивно вычислимой функции сначала описывают понятие алгоритма ( алгоритм в интуитивном смысле - это точное предписание о выполнении в определенном порядке некоторой системы операций для решения всех задач данного типа), а затем называют интуитивно вычислимой ту функцию, для которой существует алгоритм ( в интуитивном смысле) вычисления ее значений. [31]
Неосторожной формой основного тезиса было бы утверждение, гласящее, что всякий алгоритм в интуитивном смысле является алгоритмом в широком смысле. От подобной формулировки следует воздержаться. [32]
Одна часть тезиса Поста очевидна - всякий алгоритм Поста является несомненно и алгоритмом в интуитивном смысле. [33]
Таким образом, естественно считать, что любое полное К-множество является и множеством в интуитивном смысле. [34]
SxA в А; б-функция из SxR в множество П, П, ОСТАНОВ, интуитивный смысл которого станет ясен из дальнейшего. [35]
Тьюринга машины, а принцип нормализации Марко-ва - в том, что всякая вычислимая в интуитивном смысле функция вычислима с помощью нек-рого нормального ал-горифма. Тезис Черча не может быть строго доказан, так как в его формулировке участвует неточное понятие алгоритм в интуитивном смысле. [36]
ЧЕРЧА ТЕЗИС - принцип, согласно к-рому класс функций, вычислимых с помощью алгоритмов я широком интуитивном смысле, совпадает с классом частично рекурсивных функции. Все известные в математике примеры алгоритмов удовлетворяют ему. Тез и с Т ь ю-ринга заключается в том, что всякая вычислимая в интуитивном смысле функция вычислима с помощью нек-рой Тьюринга машины, а принцип нормализации Маркова - в том, что всякая вычислимая в интуитивном смысле функция вычислима с помощью нек-рого нормального алгорифма. Тезис Черча не может быть строго доказан, так как в его формулировке участвует неточное понятие алгоритм в интуитивном смысле. [37]
Заканчивая наше краткое исследование коллективов алгоритмов, заметим, что коллективы алгоритмов безусловно являются алгоритмами в интуитивном смысле, во всяком случае, если входящие в них одиночные алгоритмы не слишком сложны. Но насколько объекты, изучаемые аналитической теорией алгоритмов, сложнее тех избранных алгоритмов, которые рассматриваются логическими теориями. [38]
Всякая вычислительная процедура, к-рая может быть сведена к работе подходящей машины Тьюринга, является эффективной в интуитивном смысле. Этот тезис нельзя доказать, так как он объединяет два понятия - строгое математич. [39]
Мы начнем с простейших опытов, таких, как бросание монеты или кости, где все утверждения имеют очевидный интуитивный смысл. Эта интуиция будет переведена на язык абстрактной модели, которая будет затем обобщена на более сложные случаи. [40]
Мы начнем с простейших опытов, таких, как бросание монеты или игральной кости, где все утверждения имеют очевидный интуитивный смысл. Эти интуитивные соображения будут переведены на язык некоторой абстрактной модели, которая будет обобщаться постепенно, шаг за шагом. [41]
Отношения совершенного строгого ( или нестрогого) порядка на бесконечных множествах тоже задают, устанавливают некоторые порядки ( в интуитивном смысле) на своих областях задания, однако выразить этот факт с помощью точного утверждения трудно, так как у нас нет аналога понятия перестановки для бесконечных множеств. [42]
Но с точки зрения традиционных теорий алгоритмов программы для ЭВМ и алгоритмов на входных языках программирования являются только алгоритмами в интуитивном смысле. Традиционные теории алгоритмов заставляют при решении проблем, возникающих в связи с программированием, погружаться в туман интуиции. Программисты начинают принимать облик художников, фантазеров, творцов программ, чуть ли не волшебников. Такое положение самих программистов не устраивает. [43]
Но тогда для каждого п мы могли бы вычислить р ( п): функция р оказалась бы вычислимой в интуитивном смысле, если бы существовал алгоритм определения неостанавливающихся вычислений - процедура, обязательно заканчивающаяся через то или иное конечное число шагов независимо от того, к какой из неостанавливающихся машин ее применяют. [44]
Например, к отношениям строгого порядка принадлежит даже пустое отношение Ом ( пример 15): никакие два элемента не сравнимы по этому отношению, никакого порядка ( в интуитивном смысле) это отношение не устанавливает. Тем не менее отношения строгого ( и нестрогого) порядка, не являющиеся совершенными строгими ( соответственно, нестрогими) порядками, все-таки задают, устанавливают некоторый порядок в обобщенном смысле) ( в крайнем, вырожденном случае - никакой, пустой порядок) на своих областях задания. Добавим к примерам 3 - 15 еще несколько. [45]