Вычисление

Вычисление — это любой тип арифметических или неарифметических вычислений . четко определенный ^[1]^[2] Типичными примерами вычислений являются решение математических уравнений и выполнение компьютерных алгоритмов .

Механические или электронные устройства (или, исторически , люди), выполняющие вычисления, известны как компьютеры . Информатика — это область, которая занимается изучением вычислений.

Введение

Идея о том, что математические утверждения должны быть «четко определенными», обсуждалась математиками, по крайней мере, с 1600-х годов . ^[3] но согласие по подходящему определению оказалось невозможным. ^[4] Кандидатское определение было предложено независимо несколькими математиками в 1930-х годах. ^[5] Самый известный вариант был формализован математиком Аланом Тьюрингом , который определил четко определенное утверждение или вычисление как любое утверждение, которое можно выразить через параметры инициализации машины Тьюринга . ^[6] Другие (математически эквивалентные) определения включают Алонзо Чёрча , лямбда-определимость общую - Гёделя - Клин и Эрбрана рекурсивность 1 Эмиля Поста -определимость . ^[5]

Сегодня любое формальное утверждение или вычисление, демонстрирующее это качество четкости, называется вычислимым , а само утверждение или вычисление называется вычислением .

Определение Тьюринга приписывало «четкость» очень большому классу математических утверждений, включая все правильно построенные алгебраические утверждения и все утверждения, написанные на современных языках компьютерного программирования. ^[7]

Несмотря на широкое распространение этого определения, существуют некоторые математические концепции, которые не имеют четкой характеристики в соответствии с этим определением. Это включает в себя проблему остановки и занятую игру бобра . Остается открытым вопрос, существует ли более мощное определение понятия «четко определенное», которое способно охватить как вычислимые, так и «невычислимые» утверждения. ^{[примечание 1]}^[8]

Некоторые примеры математических утверждений, которые можно вычислить, включают:

Все операторы, характерные для современных языков программирования, включая C++ , Python и Java . ^[7]
Все расчеты осуществляются с помощью электронной вычислительной машины , калькулятора или счетов .
Все расчеты проведены на аналитической машине .
Все расчеты проводились на машине Тьюринга .
Большинство математических утверждений и расчетов дано в учебниках по математике.

Некоторые примеры математических утверждений, которые не являются вычислимыми, включают:

Расчеты или утверждения, которые нечетко определены и не могут быть однозначно закодированы в машине Тьюринга: («Пол любит меня в два раза больше, чем Джо»).
Постановки задач, которые кажутся четко определенными, но для которых можно доказать, что не существует машины Тьюринга для их решения (например, проблема остановки ).

Физический процесс вычислений

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

Альтернативные версии вычислений

Картографический аккаунт

Альтернативное объяснение вычислений можно найти в работах Хилари Патнэм и других. Питер Годфри-Смит назвал это «простым картографическим отчетом». ^[9] В резюме этого отчета Гуалтьеро Пиччинини говорится, что о физической системе можно сказать, что она выполняет определенное вычисление, когда существует отображение между состоянием этой системы и вычислением, такое, что «микрофизические состояния [системы] отражают переходы состояний между вычислительные состояния». ^[10]

Семантический счет

Такие философы, как Джерри Фодор ^[11] предложили различные объяснения вычислений с тем ограничением, что семантическое содержание является необходимым условием вычислений (то есть произвольную физическую систему отличает от вычислительной системы то, что операнды вычислений что-то представляют). Это понятие пытается предотвратить логическую абстракцию картографической теории панкомпьютационализма , идею о том, что все, можно сказать, является вычислением всего.

Механистический счет

Гуалтьеро Пиччинини предлагает объяснение вычислений, основанное на механической философии . В нем говорится, что физические вычислительные системы — это типы механизмов, которые по своей конструкции выполняют физические вычисления или манипулирование (с помощью функционального механизма) «независимым от среды» транспортным средством в соответствии с правилом. «Средняя независимость» требует, чтобы свойство могло быть создано. ^{[ нужны разъяснения ]} несколькими реализаторами ^{[ нужны разъяснения ]} и множественных механизмов, и что входы и выходы механизма также могут быть многократно реализуемы . Короче говоря, независимость от среды позволяет использовать физические переменные со свойствами, отличными от напряжения (как в типичных цифровых компьютерах); это необходимо при рассмотрении других типов вычислений, например тех, которые происходят в мозге или в квантовом компьютере . В этом смысле правило обеспечивает сопоставление входов, выходов и внутренних состояний физической вычислительной системы. ^[12]

Математические модели

В теории вычислений разработано множество математических моделей вычислений.Типичными математическими моделями компьютеров являются следующие:

Модели состояний, включая машину Тьюринга , автомат с выталкиванием , конечный автомат и PRAM.
Функциональные модели, включая лямбда-исчисление
Логические модели, включая логическое программирование
Параллельные модели, включая модель актера и исчисление процессов.

Джунти называет модели, изучаемые теорией вычислений, вычислительными системами и утверждает, что все они являются математическими динамическими системами с дискретным временем и дискретным пространством состояний. ^[13]^{: гл.1} Он утверждает, что вычислительная система — это сложный объект, состоящий из трех частей. Во-первых, математическая динамическая система $DS$ с дискретным временем и дискретным пространством состояний; во-вторых, вычислительная установка $H=\left(F,B_{F}\right)$ , который состоит из теоретической части $F$ и действительная часть $B_{F}$ ; в-третьих, интерпретация $I_{DS,H}$ , который связывает динамическую систему $DS$ с настройкой $H$ . ^[14]^{: стр. 179–80.}

См. также

Примечания

^ Исследование невычислимых утверждений — это область гипервычислений .

Ссылки

^ Расчеты из бесплатного словаря Merriam-Webster.
^ «Вычисления: определение и синонимы с сайта Answers.com» . Ответы.com . Архивировано из оригинала 22 февраля 2009 года . Проверено 26 апреля 2017 г. .
^ Кутюра, Луи (1901). Логика Лейбница по неопубликованным документам . Париж. ISBN 978-0343895099 .
^ Дэвис, Мартин; Дэвис, Мартин Д. (2000). Универсальный компьютер . WW Нортон и компания. ISBN 978-0-393-04785-1 .
^ Jump up to: ^а ^б Дэвис, Мартин (1 января 1982 г.). Вычислимость и неразрешимость . Курьерская корпорация. ISBN 978-0-486-61471-7 .
^ Тьюринг, AM (1937) [доставлен Обществу в ноябре 1936 года]. «О вычислимых числах с применением к проблеме Entscheidungs» (PDF) . Труды Лондонского математического общества . 2. Том. 42. С. 230–65. дои : 10.1112/plms/s2-42.1.230 .
^ Jump up to: ^а ^б Дэвис, Мартин; Дэвис, Мартин Д. (2000). Универсальный компьютер . WW Нортон и компания. ISBN 978-0-393-04785-1 .
^ Дэвис, Мартин (2006). «Почему нет такой дисциплины, как гиперкомпьютер». Прикладная математика и вычислительная техника . 178 (1): 4–7. дои : 10.1016/j.amc.2005.09.066 .
^ Годфри-Смит, П. (2009), «Аргументы тривиальности против функционализма», Philosophical Studies , 145 (2): 273–95, doi : 10.1007/s11098-008-9231-3 , S2CID 73619367
^ Пиччинини, Гуальтьеро (2015). Физические вычисления: механистический счет . Оксфорд: Издательство Оксфордского университета. п. 18. ISBN 9780199658855 .
^ Фодор, Дж. А. (1986), «Проблема разума и тела», Scientific American , 244 (январь 1986 г.)
^ Пиччинини, Гуальтьеро (2015). Физические вычисления: механистический счет . Оксфорд: Издательство Оксфордского университета. п. 10. ISBN 9780199658855 .
^ Джунти, Марко (1997). Вычисления, динамика и познание . Нью-Йорк: Издательство Оксфордского университета. ISBN 978-0-19-509009-3 .
^ Джунти, Марко (2017), «Что такое физическая реализация вычислительной системы?» , Изономия - Эпистемология , 9 : 177–92, ISSN 2037-4348.

[8] Исследование невычислимых утверждений — это область гипервычислений .

[1] Расчеты из бесплатного словаря Merriam-Webster.

[2] «Вычисления: определение и синонимы с сайта Answers.com» . Ответы.com . Архивировано из оригинала 22 февраля 2009 года . Проверено 26 апреля 2017 г. .

[3] Кутюра, Луи (1901). Логика Лейбница по неопубликованным документам . Париж. ISBN 978-0343895099 .

[Davis_Davis_2000-4] Дэвис, Мартин; Дэвис, Мартин Д. (2000). Универсальный компьютер . WW Нортон и компания. ISBN 978-0-393-04785-1 .

[Davis-5] Jump up to: ^а ^б Дэвис, Мартин (1 января 1982 г.). Вычислимость и неразрешимость . Курьерская корпорация. ISBN 978-0-486-61471-7 .

[6] Тьюринг, AM (1937) [доставлен Обществу в ноябре 1936 года]. «О вычислимых числах с применением к проблеме Entscheidungs» (PDF) . Труды Лондонского математического общества . 2. Том. 42. С. 230–65. дои : 10.1112/plms/s2-42.1.230 .

[Davis_Davis_2000_p.-7] Jump up to: ^а ^б Дэвис, Мартин; Дэвис, Мартин Д. (2000). Универсальный компьютер . WW Нортон и компания. ISBN 978-0-393-04785-1 .

[9] Дэвис, Мартин (2006). «Почему нет такой дисциплины, как гиперкомпьютер». Прикладная математика и вычислительная техника . 178 (1): 4–7. дои : 10.1016/j.amc.2005.09.066 .

[10] Годфри-Смит, П. (2009), «Аргументы тривиальности против функционализма», Philosophical Studies , 145 (2): 273–95, doi : 10.1007/s11098-008-9231-3 , S2CID 73619367

[11] Пиччинини, Гуальтьеро (2015). Физические вычисления: механистический счет . Оксфорд: Издательство Оксфордского университета. п. 18. ISBN 9780199658855 .

[12] Фодор, Дж. А. (1986), «Проблема разума и тела», Scientific American , 244 (январь 1986 г.)

[13] Пиччинини, Гуальтьеро (2015). Физические вычисления: механистический счет . Оксфорд: Издательство Оксфордского университета. п. 10. ISBN 9780199658855 .

[14] Джунти, Марко (1997). Вычисления, динамика и познание . Нью-Йорк: Издательство Оксфордского университета. ISBN 978-0-19-509009-3 .

[15] Джунти, Марко (2017), «Что такое физическая реализация вычислительной системы?» , Изономия - Эпистемология , 9 : 177–92, ISSN 2037-4348.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[примечание 1]

[8]

[9]

[10]

[11]

[12]

[13]

[14]