Краткая история теоретического подхода компьютерной науки к вычислениям

Таблица ссылок

Аннотация и 1 Введение

2 Краткий обзор CtmR, робота с мозгом CTM

2.1 Формальное определение CtmR

2.2 Сознательное внимание в CtmR

2.3 Осознанное осознание и чувство сознания в CtmR

2.4 CtmR как основа для общего искусственного интеллекта (AGI)

3. Соответствие CtmR другим теориям сознания

4 Ответы на вопросы Кевина Митчелла с точки зрения CtmR

5. Резюме и выводы

6 Благодарности

7 Приложение

7.1 Краткая история теоретического подхода компьютерной науки к вычислениям

7.2 Вероятностная конкуренция за сознательное внимание и влияние на него диспозиции

Ссылки

7.1 Краткая история теоретического подхода компьютерной науки к вычислениям

Теоретический подход компьютерной науки к вычислениям начался с Алана Тьюринга в 1930-х годах и фокусировался на вопросе: «Что вычислимо (разрешимо), а что нет?» (Тьюринг, 1937). Тьюринг определил простую формальную модель вычислений, которую мы теперь называем машиной Тьюринга (МТ), и определил функцию как вычислимую тогда и только тогда, когда она может быть реализована как карта ввода-вывода МТ. Формальное определение МТ (программы) также дает формальное определение неформальной концепции алгоритма.

Используя свою модель, Тьюринг доказал свойства (теоремы) вычислимых функций, включая существование универсальных вычислимых функций (универсальных машин Тьюринга) и тот факт, что некоторые функции невычислимы. Первое предвидит реализацию универсальных программируемых компьютеров; второе — что некоторые проблемы не могут быть решены даже самыми мощными компьютерами. Например, Тьюринг показывает, что не существует машины Тьюринга (вычислимой функции Тьюринга), которая при заданном описании ТМ M и входных данных x выдает 1, если M на входных данных x (в конце концов) останавливается, и 0, если нет. Это известно как «проблема остановки» и эквивалентно теореме Гёделя о неразрешимости арифметики.

Но почему мы должны верить в Тезис Чёрча-Тьюринга, впервые предложенный в (Тьюринг, 1937), что ТМ воплощает неформальное понятие вычислимости (разрешимости)? Это потому, что каждая из множества очень разных независимо определенных моделей дискретных вычислений, включая ТМ и эффективную вычислимость Алонзо Чёрча (Чёрч, 1936), определяет в точности один и тот же класс функций, вычислимых функций. На языке программирования все достаточно мощные практические языки программирования эквивалентны в том, что любой из них может имитировать (компилироваться) любой другой. Вытекающая из этого математическая теория часто называется Теорией вычислений (ТОВ).

В 1960-х годах, с более широкой доступностью компьютеров, новоиспеченные ученые-теоретики, такие как Джек Эдмондс (Edmonds, 1965) и Ричард Карп (Karp, 1972), указали на то, что ресурсы имеют значение. Некоторые проблемы, которые в принципе были разрешимы, казались неразрешимыми при наличии осуществимых временных и пространственных ресурсов. Более того, неразрешимость, казалось, была внутренним свойством проблемы, а не метода решения или реализующей машины. Последующая подтеория TOC, которая вводит ограничения ресурсов в то, что вычислимо или невычислимо эффективно, называется Теоретической информатикой (TCS).

TCS фокусируется на вопросе: «Что вычислимо (разрешимо) или невычислимо) при ограниченных ресурсах?» Ключевой проблемой здесь является обманчиво простая «проблема SAT»: дана булева формула �, выполнима ли она, то есть существует ли присвоение истинности ее переменным, которое делает формулу � истинной? Эта проблема разрешима. Вот процедура принятия решения: дана булева формула � с n переменными, систематически проверяйте, делает ли любое из 2n возможных присвоений истинности формулу истинной. Если да, выведите 1, в противном случае выведите 0. Эта процедура грубой силы занимает экспоненциальное (n) время в общем случае. Но является ли «проблема SAT» разрешимой, то есть разрешимой эффективно, т. е. за полиномиальное (n) время? Это эквивалентно известной проблеме P = NP? (Кук, 1971), (Карп, 1972), (Левин, 1973).

Разработка новых и эффективных алгоритмов является ключевым направлением деятельности TCS.

Переворачивая ситуацию с ног на голову, способность использовать силу сложных проблем, проблем, которые невозможно решить эффективно, стала ключевым пониманием TCS. Примером может служить определение псевдослучайности. Эта способность использовать силу сложности является новой для математики.