Вычисление

Вычисление — тип арифметических или неарифметических вычислений . это любой четко определенный ^[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 .
^ Перейти обратно: ^а ^б Дэвис, Мартин (1 января 1982 г.). Вычислимость и неразрешимость . Курьерская корпорация. ISBN 978-0-486-61471-7 .
^ Тьюринг, AM (1937) [доставлен Обществу в ноябре 1936 года]. «О вычислимых числах с применением к проблеме Entscheidungs» (PDF) . Труды Лондонского математического общества . 2. Том. 42. С. 230–65. дои : 10.1112/plms/s2-42.1.230 .
^ Перейти обратно: ^а ^б Дэвис, Мартин; Дэвис, Мартин Д. (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] Перейти обратно: ^а ^б Дэвис, Мартин (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] Перейти обратно: ^а ^б Дэвис, Мартин; Дэвис, Мартин Д. (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]