Навигация
ОбложкаЕршов Ю.Л. Алгоритмы и вычислимость в человеческом познании / Ю.Л.Ершов, В.В.Целищев; отв ред. К.Ф.Самохвалов, А.С.Морозов; Рос. акад. наук, Сиб. отд-ние, Ин-т математики, Ин-т философии и права. - Новосибирск: Изд-во СО РАН, 2012. - 504 с. - (Интеграционные проекты СО РАН; вып.40)
Оглавление книги
Глава 1  ВЫЧИСЛИМОСТЬ И НЕВЫЧИСЛИМОСТЬ .......................... 5
Рекурсивность и вычислимость .................................... -
Алгоритм, эффективно вычислимая функция и рекурсивность ......... 6
Алгоритмы и знание .............................................. 8
Невычислимость ................................................. 12
Практическая невычислимость .................................... 13
Невычислимость, редукционизм и холизм .......................... 16
Физикализм, бесконечность и невычислимость ..................... 18
Компьютерная модель вселенной .................................. 20
Машинная невычислимость и человеческая вычислимость ............ 22
Вычисления и алгоритмы ......................................... 23
Структура диагонального аргумента Пенроуза ..................... 26
Истина и алгоритм .............................................. 27
Простота алгоритма и возникновение сложности ................... 30

Глава 2  МАТЕМАТИЧЕСКИЙ АППАРАТ ВЫЧИСЛИМОСТИ ................... 32
Рекурсивные функции и основания математики ..................... --
Примитивно рекурсивные функции ................................. 33
Функция Аккермана .............................................. 35
Финитизм и примитивно рекурсивная арифметика ................... 37
Поиск более общего понятия - общерекурсивные функции Геделя .... 39
Эволюция рекурсивности ......................................... 42
Неразрешимость и λ-определимость ............................... --
Алгоритмы и λ-исчисление ....................................... 44

Глава 3  ИНТУИЦИЯ, ФИНИТИЗМ И ПРИМИТИВНО РЕКУРСИВНЫЕ ФУНКЦИИ ... 47
Терминологические замечания .................................... --
Основные направления исследований соотношения ПРА и финитизма .. 48
Финитизм и минимальный вид мышления ............................ 49
Эпистемологический статус объектов финитизма ................... 50
Финитизм: онтология и эпистемология ............................ 51
Финитарность ................................................... 52
Простота и вычисления .......................................... 54
Тезис Гильберта ................................................ 56
Финитизм и интуитивное знание .................................. 57
Интуитивность операций сложения и умножения .................... 58
Обоснованность тезиса Гильберта ................................ 59
Финитизм и понятие функции ..................................... 61
Финитизм и понятие числа ....................................... 62
Тезис Тейта .................................................... 64
Сфера действия финитизма и рекурсивные функции ................. 65
Контрпримеры финитизму! ........................................ 67
Если не интуиция, то что? ...................................... 69

Глава 4  ФИНИТИЗМ И ОСНОВАНИЯ МАТЕМАТИКИ ....................... 72
Математика и философия ......................................... --
Финитизм Гильберта и интуиция .................................. 73
Финитизм и программа Гильберта ................................. 75
Семантика финитизма ............................................ 81
Финитизм как основания математики .............................. 84
Финитизм и непротиворечивость формальной системы ............... 86
Математика и логика как основания математики ................... 87

Глава 5  АПРИОРИЗМ И ФЕНОМЕНОЛОГИЯ МАТЕМАТИЧЕСКОЙ ИНТУИЦИИ ..... 90
Кантовская теория интуиции ..................................... --
Сингулярность интуиции ......................................... 91
Игровая интерпретация кванторов и индивиды ..................... 93
Логика и интуиция .............................................. 97
Гильберт и Кант ............................................... 100
Кантианская притча Эддингтона ................................. 101
Интуитивное, логическое и символическое ....................... 102
Феноменология и интенциональность ............................. 106
Интуиция и интенция ........................................... 109
Интенции и конструкции ........................................ 111
Феноменология алгоритма ....................................... 112
Виды конструирования .......................................... 114
Интенциональность как интенсиональность ....................... 117

Глава 6  МАТЕМАТИЧЕСКАЯ ИНДУКЦИЯ И МИНИМАЛЬНЫЕ СРЕДСТВА
МАТЕМАТИЧЕСКОГО МЫШЛЕНИЯ ...................................... 120
Логика и базис математического мышления ....................... ---
Натуральные числа ............................................. 121
Аксиомы Пеано ................................................. 123
Нестандартные интерпретации ................................... 124
Статус пятой аксиомы Пеано .................................... 127
Система Q ..................................................... 128
Математическая индукция как экономия мышления ................. 130
Математическая индукция как определение натуральных чисел ..... 132
Индукция и интуиция ........................................... 135
Финитизм и математическая индукция ............................ 137
Обозримость и формализуемость математических структур ......... 140
Индукция и минимальные средства математического мышления ...... 143
Математическая индукция и пределы эмпиризма ................... 144
Интуиция процесса конструирования ............................. 146
Априоризм и феноменология ..................................... 147
Феноменология математической индукции ......................... 149

Глава 7  ДОКАЗАТЕЛЬСТВО И РАЦИОНАЛЬНОЕ МЫШЛЕНИЕ ............... 150
Доказательство и диалектика ................................... ---
Понимание без доказательства: математические метафоры ......... 154
Осмысленность доказательства .................................. 158
Рациональность математического рассуждения .................... 162
Теоретические ограничения на математическую аргументацию ...... 165
Значение и интерпретация ...................................... 167
Неопределенность указания в языке ............................. 168
Интерпретация и объяснение в математическом языке ............. 169
Значение как употребление ..................................... 171

Глава 8  ОБОЗРИМОСТЬ ДОКАЗАТЕЛЬСТВА ........................... 174
Обозримость дедукции у Бэкона и Декарта ....................... ---
Локальная и глобальная обозримость ............................ 177
Обозримость доказательства в аналитической философии .......... 179
Обозримость и формализуемость ................................. 181
Обозримость и рациональность .................................. 182
Три характеристики доказательства ............................. 184
Обозримость и эмпиризм ........................................ 185
Доказательство и проверка доказательства ...................... 187
Соотношение обозримости и формализации ........................ 188
Дихтомии локальная - глобальная обозримость и комбинаторное
доказательство-озарение ....................................... 189

Глава 9  ВЫЧИСЛИМОСТЬ И ДОКАЗАТЕЛЬСТВО ........................ 192
Элементарный шаг дедукции и вычисление ........................ ---
Когнитивный акт versus эмпирическая процедура ................. 195
Дедукция как вычисление ....................................... 199
Элементарность дедуктивного шага .............................. 202

Глава 10 ЭПИСТЕМОЛОГИЧЕСКИЕ ВЕРСИИ ТЕЗИСА А. ЧЕРЧА ............ 204
Истоки и различные формулировки тезиса Черча .................. ---
Попытки обосновать тезис Черча ................................ 205
Возражения против тезиса ...................................... 207
Можно ли доказать тезис Черча? ................................ 209
Доказательство тезиса! ........................................ 211
Тезис как определение ......................................... 214
Интуиция и формализация ....................................... 216
Модальности в математике ...................................... 217
Структурализм и супертезис .................................... 218
Нормативность и экспликация ................................... 219

Глава 11 ЭФФЕКТИВНАЯ ВЫЧИСЛИМОСТЬ ............................. 222
Вычисление как операция, производимая человеком ............... ---
"Человеческая" версия тезиса Черча ............................ 223
Неполнота и эффективная вычислимость .......................... 224
Пошаговый аргумент Черча ...................................... ---
Дедукция и эффективность процедур ............................. 226
Тезис Тьюринга ................................................ 229
Машинная версия тезиса ........................................ 231
Абсолютность .................................................. 232
Тезис Ганди  .................................................. 234
Физический тезис Ч-Т (ФТЧТ) ................................... 237

Глава 12 ИСТОРИЯ ТЕЗИСА ЧЕРЧА ................................. 238
Аксиоматика, алгоритмы и механизм ............................. ---
Рождение тезиса ............................................... 240
Как был воспринят тезис Черча? ................................ 242
Социология ярлыков ............................................ 244
Судьба тезиса Черча ........................................... 247

Глава 13 ЭФФЕКТИВНОСТЬ МАТЕМАТИЧЕСКАЯ И ОБЫДЕННАЯ ............. 251
Эффективные вычисления и эффективные процедуры ................ ---
Эффективность машины Тьюринга ................................. 253
Структура и разновидности тезиса Черча - Тьюринга ............. 256
Иерархия тезисов .............................................. 258
Операции с абстрактными и физическими символами ............... 260
Вычисление функций ............................................ 262
Причинные и формальные манипуляции с символами ................ 265

Глава 14 МАТЕМАТИКА И МЫШЛЕНИЕ ................................ 268
Два направления в понимании проблемы алгоритмизации мышления .. ---
Математическая логика, мозг и компьютер ....................... 270
Генезис и постановка проблемы ................................. 273
Методология философских заключений из математических
результатов ................................................... 274
Гедель: философия и математика ................................ 277
Дилемма Геделя ................................................ 279
Анализ дилеммы ................................................ 282
Машины, математики и математические предложения ............... 285
Лукас, Пенроуз и Гедель ....................................... 286

Глава 15 ЧЕЛОВЕК, МАШИНА И ГЕДЕЛЕВО ПРЕДЛОЖЕНИЕ ............... 289
Математические результаты и метафизика ........................ ---
Аргумент Лукаса ............................................... 291
Экспликация менталистского аргумента .......................... 292
Критика Бенацеррафом аргумента Лукаса ......................... 295
Следует ли формализовать аргумент Лукаса? ..................... 300
Возражение в стиле Дж. Мура ................................... 303
Диалектика первого и третьего лица ............................ ---
Бремя доказательства непротиворечивости ....................... 306
Нормативное постулирование непротиворечивости ................. 308
Эмпирическая природа установления непротиворечивости .......... 309
Металингвистические соображения относительно
непротиворечивости ............................................ 310

Глава 16 ТРАНСФИНИТНЫЙ АРГУМЕНТ И ПРИНЦИПЫ РЕФЛЕКСИИ .......... 314
Трансфинитное расширение системы .............................. ---
Игра человека с компьютером ................................... 315
Расширение системы и понимание ................................ 316
Теорема Клини - Черча ......................................... 318
Антропоцентризм и человеческие возможности .................... 319
Геделево предложение как принцип рефлексии .................... 321
Непротиворечивость как принцип рефлексии ...................... 322
Сильные принципы рефлексии и неестественное расширение
системы ....................................................... 324
Алгоритмы и геделизация ....................................... 325
Формализация и "скачки" в мышлении ............................ 329
Принцип рефлексии для рекурсивных ординальных чисел ........... 330
Рационалистический оптимизм Геделя ............................ 333

Глава 17 КОМПЬЮТЕР, ИСТИНА И ДОКАЗУЕМОСТЬ ..................... 335
"Видение" истины .............................................. ---
"Пиление" истины геделева предложения машиной Тьюринга и
человеком ..................................................... 339
Расхождение истины и доказательства ........................... 340
Ничья в игре между человеком и машиной ........................ 344
Синтаксические и семантические характеристики формальных
систем ........................................................ 346
Оператор доказуемости ......................................... 347
"Знание" машины ............................................... 349
Оператор истины ............................................... 351
Соn(T) как дополнительная аксиома и принцип рефлексии ......... 352
Более мощные логические системы ............................... 355
Машина Тьюринга знает свое геделево предложение ............... 357

Глава 18 АЛГОРИТМИЧЕСКАЯ ВЕРСИЯ МЕНТАЛИЗМА .................... 359
Вычисления и алгоритмы ........................................ ---
Диагональный аргумент Пенроуза ................................ 363
Истина и алгоритм ............................................. 366
Платонизм и истинность геделева предложения ................... 368
Обоснованность формальной системы и мышление .................. 371
Неосознаваемый факт эквивалентности алгоритма и мышления ...... 372
Сводка аргумента Пенроуза о неосознаваемости эквивалентности
ума машине .................................................... 373
Как следует понимать формальную систему, симулирующую ум? ..... 374
Неопровержимость математических истин ......................... 377
Новый аргумент Пенроуза ....................................... 378
Еще одна версия "нового" аргумента Пенроуза ................... 382

Глава 19 НЕПРОТИВОРЕЧИВОСТЬ И ПОЛНОТА ......................... 388
Логика и мышление ............................................. ---
Теоремы Геделя о неполноте .................................... 389
Интермедия: короткое доказательство Булоса второй теоремы
о неполноте  .................................................. 390
Сфера и причина ограничений в "ограничительных" теоремах
Геделя ........................................................ 392
Локальная и глобальная непротиворечивость ..................... 394
Судьбы непротиворечивости арифметики .......................... 397
Относительность обоснованности ................................ 398
Эмпирические и дедуктивные факторы в обнаружении
непротиворечивости ............................................ 400
Неопровержимость знания о собственной непротиворечивости ...... 401
Противоречиво ли человеческое мышление? ....................... 403
Полнота формальной системы .................................... 406
Различные виды полноты ........................................ 408
Какого рода неполнота имеется в виду в теоремах Геделя ........ 409

Глава 20 ИСТИННОСТЬ ГЕДЕЛЕВА ПРЕДЛОЖЕНИЯ ...................... 412
Три взгляда на причину истинности геделева предложения ........ ---
Истинность и непротиворечивость ............................... 413
Стандартная интерпретация ..................................... 414
Нестандартные модели .......................................... 416
Структура геделева предложения ................................ 418
"Семантический" аргумент ...................................... 419
"Дефляционная" теория истины .................................. 421
Неразрешимость и семантический аргумент ....................... 424
Истина и выразительные возможности языка ...................... 425
Предикат истины и консервативность расширения системы ......... 427
Принципы рефлексии и истина ................................... 428
Аналитические и синтетические математические истины ........... 431
Познаваемость математических истин ............................ 433

Глава 21 ЧЕЛОВЕЧЕСКАЯ МАТЕМАТИКА .............................. 437
Геделево предложение и платонизм .............................. ---
Объективная и субъективная математика ......................... 438
Дедуктивный базис человеческой математики ..................... 440
Некомпьютерный характер мышления .............................. 443
Эффективность рационального мышления .......................... 446
Окончательные правила ......................................... 448
Прямой доступ к истине ........................................ 450
Математическое мышление и рекурсивные функции ................. 454
Неполнота и кодирование ....................................... 457
Роль принципа рефлексии в постижении бесконечного ............. 459
Самореференция и кодирование .................................. 461
Теорема Гудстейна и человеческая математика ................... 463
Геделево предложение и человеческая математика ................ 467

Глава 22 "СОЗНАНИЕ" МАШИНЫ .................................... 469
Эпистемическая и теоретико-доказательная интерпретации ........ ---
Самосознание машины ........................................... 471
Стадии самоосознания .......................................... 475
Регулярность, нормальность и непротиворечивость ............... 477
Сводка результатов ............................................ 480
Рефлексивность  ............................................... 481
Неподвижные точки ............................................. 483
Стабильная система ............................................ 484
Логические машины ............................................. 486

СПИСОК ЛИТЕРАТУРЫ ............................................. 490

Настоящая монография представляет собой итог исследований по проблеме алгоритмизации мышления, которая часто увязывается с распространенной формулировкой «может ли машина мыслить?» В монографии представлены практически все аспекты проблемы понимания деятельности, связанной с вычислимостью и компьютерными методами исследования возможностей мышления.
Дано сопоставление вычислимости и невычислимости в контексте методов познания законов природы. Описан математический аппарат вычислимости, в частности, представлена теория рекурсивных функций. Особое внимание уделено связи этой теории с программой оснований математики Д.Гильберта - финитизмом. Процесс алгоритмизации мышления представлен в терминах минимальных средств строгого математического доказательства. При этом обнаружена проблема обозримости доказательства, а также вычислимости как средства получения доказательства. Понятие эффективной вычислимости обсуждено в связи со статусом тезиса Черча, который долгое время был предметом дискуссий.
Монография предназначена специалистам в области компьютерных исследований, математической логики, философии, логики и методологии науки.

Выпуски
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
36 37 38 39 40 41 42 43 44 45 46 47                                              


[О библиотеке | Академгородок | Новости | Выставки | Ресурсы | Библиография | Партнеры | ИнфоЛоция | Поиск | English]
  Пожелания и письма: www@prometeus.nsc.ru
© 1997-2017 Отделение ГПНТБ СО РАН (Новосибирск)
Статистика доступов: архив | текущая статистика
 

Документ изменен: Mon Apr 11 19:02:15 2016. Размер: 26,033 bytes.
Посещение N 1535 c 28.10.2013