Вычисление — это любой четко определенный тип арифметических или неарифметических вычислений . [1] [2] Распространенными примерами вычислений являются математические уравнения и компьютерные алгоритмы .
Механические или электронные устройства (или, исторически , люди), выполняющие вычисления, известны как компьютеры . Изучение вычислений — это область вычислимости , которая сама по себе является подобластью информатики .
Идея о том, что математические утверждения должны быть «четко определенными», обсуждалась математиками, по крайней мере, с 1600 -х годов [3] , но согласие по поводу подходящего определения оказалось неуловимым. [4] Кандидатское определение было предложено независимо несколькими математиками в 1930-х годах. [5] Самый известный вариант был формализован математиком Аланом Тьюрингом , который определил четко определенное утверждение или вычисление как любое утверждение, которое может быть выражено через параметры инициализации машины Тьюринга . [6] Другие (математически эквивалентные) определения включают лямбда-определимость Алонзо Чёрча , общую рекурсивность Эрбрана - Гёделя - Клин и 1 -определимость Эмиля Поста . [5]
Сегодня любое формальное утверждение или вычисление, демонстрирующее это качество четкости, называется вычислимым , а само утверждение или вычисление называется вычислением .
Определение Тьюринга приписывало «четкость» очень большому классу математических утверждений, включая все правильно построенные алгебраические утверждения и все утверждения, написанные на современных языках компьютерного программирования. [7]
Несмотря на широкое распространение этого определения, существуют некоторые математические концепции, которые не имеют четкой характеристики в соответствии с этим определением. Сюда входит проблема остановки и занятая игра бобра . Остается открытым вопрос, существует ли более мощное определение понятия «четко определенное», которое способно охватить как вычислимые, так и «невычислимые» утверждения. [примечание 1] [8]
Некоторые примеры математических утверждений, которые можно вычислить, включают:
Некоторые примеры математических утверждений, которые не являются вычислимыми, включают:
Вычисления можно рассматривать как чисто физический процесс, происходящий внутри закрытой физической системы, называемой компьютером . Доказательство Тьюринга «О вычислимых числах с применением к проблеме Entscheidungsproblem» 1937 года продемонстрировало, что существует формальная эквивалентность между вычислимыми утверждениями и конкретными физическими системами, обычно называемыми компьютерами . Примерами таких физических систем являются: машины Тьюринга , люди-математики, следующие строгим правилам, цифровые компьютеры , механические компьютеры , аналоговые компьютеры и другие.
Альтернативное объяснение вычислений можно найти в работах Хилари Патнэм и других. Питер Годфри-Смит назвал это «простым картографическим отчетом». [9] В кратком изложении этого отчета Гуалтьеро Пиччинини говорится, что о физической системе можно сказать, что она выполняет определенное вычисление, когда существует соответствие между состоянием этой системы и вычислением, такое, что «микрофизические состояния [системы] отражают состояние переходы между вычислительными состояниями». [10]
Такие философы, как Джерри Фодор [11], предложили различные объяснения вычислений с ограничением, согласно которому семантическое содержание является необходимым условием вычислений (то есть, что отличает произвольную физическую систему от вычислительной системы, так это то, что операнды вычислений что-то представляют). . Это понятие пытается предотвратить логическую абстракцию картографической теории панкомпьютационализма , идею о том, что все, можно сказать, является вычислением всего.
Гуалтьеро Пиччинини предлагает объяснение вычислений, основанное на механической философии . В нем говорится, что физические вычислительные системы — это типы механизмов, которые по своей конструкции выполняют физические вычисления или манипулирование (с помощью функционального механизма) «независимым от среды» транспортным средством в соответствии с правилом. «Средняя независимость» требует, чтобы свойство могло быть реализовано [ необходимо пояснение ] несколькими реализаторами [ необходимо пояснение ] и несколькими механизмами, а также чтобы входы и выходы механизма также были многократно реализуемыми . Короче говоря, независимость от среды позволяет использовать физические переменные со свойствами, отличными от напряжения (как в типичных цифровых компьютерах); это необходимо при рассмотрении других типов вычислений, например тех, которые происходят в мозге или в квантовом компьютере . В этом смысле правило обеспечивает сопоставление входов, выходов и внутренних состояний физической вычислительной системы. [12]
В теории вычислений разработано множество математических моделей вычислений. Типичными математическими моделями компьютеров являются следующие:
Джунти называет модели, изучаемые теорией вычислений, вычислительными системами и утверждает, что все они являются математическими динамическими системами с дискретным временем и дискретным пространством состояний. [13] : гл.1 Он утверждает, что вычислительная система представляет собой сложный объект, состоящий из трех частей. Во-первых, математическая динамическая система с дискретным временем и дискретным пространством состояний; во-вторых, вычислительная установка , состоящая из теоретической и реальной частей ; в-третьих, интерпретация , которая связывает динамическую систему с установкой . [14] : стр. 179–80.