Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

Рассмотрим известный процесс извлечения квадратного корня из положительных действительных чисел: = 18,1... J 28 I 228 8 I 224 361 I 400 1 I 361 Ясно, что если для заданного числа а число л[а является рациональным, то рано или поздно заметим период (если считать, что мы это умеем делать). Если же -/а не является рациональным числом, то, сколько бы долго ни продолжались эти вычисления, мы не сможем на основе этих вычислений сказать, будет когда-нибудь период или нет, т.е. является 4а рациональным или нет. Таким образом, эта процедура будет полуэффективной процедурой для выяснения рациональности 4а. Отметим, что в литературе по теории алгоритмов существует иное понятие эффективной процедуры (алгоритма). В теории алгоритмов иногда эффективным считается алгоритм, имеющий полиномиальную временную сложность (см. главу 7 данного пособия). Отыщи всему начало, и ты много поймешь. Козьма Прутков § 2. Дедуктивные теории Дедукция (от латинского deductic - выведение) - форма мышления, когда заключение выводится чисто логическим путем (т.е. по правилам логики) из некоторых данных посылок. Индукция (от латинского inductio - наведение) - форма мышления, посредством которой от некоторых фактов или истинных высказываний переходят к некоторой гипотезе (общему утверждению). Примеры дедуктивных рассуждений. 1. Все люди смертны. Сократ - человек. Следовательно, Сократ смертен. 2. 5> 3, 3 >1, следовательно, 5 >1. Примеры индуктивных рассуждений. 1. График функции у=2х+3 - прямая, график функции у=Зх+1 - прямая, следовательно, функции вида у=кх+Ь имеют графиком прямую. Полученная здесь гипотеза оказывается истинной. 100