Вычисление

Любой вид расчета

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

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

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Смотрите также

• Теория вычислимости
• Гипервычисления
• Вычислительная задача
• Пределы вычислений
• Вычислительность

Примечания

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

Рекомендации

1. Расчеты из бесплатного словаря Merriam-Webster.
2. «Вычисления: определение и синонимы с сайта Answers.com». Ответы.com . Архивировано из оригинала 22 февраля 2009 года . Проверено 26 апреля 2017 г. .
3. Кутюра, Луи (1901). la Logique de Leibniz a'Après des Documents Inédits . Париж. ISBN 978-0343895099.
4. Дэвис, Мартин; Дэвис, Мартин Д. (2000). Универсальный компьютер . WW Нортон и компания. ISBN 978-0-393-04785-1.
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.
7. Дэвис, Мартин; Дэвис, Мартин Д. (2000). Универсальный компьютер . WW Нортон и компания. ISBN 978-0-393-04785-1.
8. Дэвис, Мартин (2006). «Почему нет такой дисциплины, как гиперкомпьютер». Прикладная математика и вычислительная техника . 178 (1): 4–7. дои : 10.1016/j.amc.2005.09.066.
9. Годфри-Смит, П. (2009), «Аргументы тривиальности против функционализма», Philosophical Studies , 145 (2): 273–95, doi : 10.1007/s11098-008-9231-3, S2CID  73619367
10. Пиччинини, Гуальтьеро (2015). Физические вычисления: механистический счет . Оксфорд: Издательство Оксфордского университета. п. 18. ISBN 9780199658855.
11. Фодор, Дж. А. (1986), «Проблема разума и тела», Scientific American , 244 (январь 1986 г.)
12. Пиччинини, Гуальтьеро (2015). Физические вычисления: механистический счет . Оксфорд: Издательство Оксфордского университета. п. 10. ISBN 9780199658855.
13. Джунти, Марко (1997). Вычисления, динамика и познание . Нью-Йорк: Издательство Оксфордского университета. ISBN 978-0-19-509009-3.
14. Джунти, Марко (2017), «Что такое физическая реализация вычислительной системы?», Isonomia – Epistemologica , 9 : 177–92, ISSN  2037-4348