Вычисление
Любой тип расчета

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

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

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

Введение

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

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

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

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

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

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

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

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

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

Альтернативные способы вычисления

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

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

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

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

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

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

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

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

Джунти называет модели, изучаемые теорией вычислений, вычислительными системами и утверждает, что все они являются математическими динамическими системами с дискретным временем и дискретным пространством состояний. [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. ^ "Определение ВЫЧИСЛЕНИЯ". www.merriam-webster.com . 2024-10-11 . Получено 2024-10-12 .
  2. ^ "Computation: Definition and Synonyms from Answers.com". Answers.com . Архивировано из оригинала 22 февраля 2009 . Получено 26 апреля 2017 .
  3. ^ Кутюра, Луи (1901). la Logique de Leibniz a'Après des Documents Inédits . Париж. ISBN 978-0343895099.
  4. ^ Дэвис, Мартин; Дэвис, Мартин Д. (2000). Универсальный компьютер . WW Norton & Company. ISBN 978-0-393-04785-1.
  5. ^ ab Davis, Martin (1982-01-01). Вычислимость и неразрешимость . Courier Corporation. ISBN 978-0-486-61471-7.
  6. ^ Turing, AM (1937) [Представлено Обществу в ноябре 1936 г.]. "О вычислимых числах с приложением к Entscheidungsproblem" (PDF) . Труды Лондонского математического общества . 2. Том 42. С. 230–65. doi :10.1112/plms/s2-42.1.230.
  7. ^ ab Дэвис, Мартин; Дэвис, Мартин Д. (2000). Универсальный компьютер . WW Norton & Company. ISBN 978-0-393-04785-1.
  8. ^ Дэвис, Мартин (2006). «Почему нет такой дисциплины, как гипервычисления». Прикладная математика и вычисления . 178 (1): 4–7. doi :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. ^ Piccinini, Gualtiero (2015). Физические вычисления: механистический счет . Оксфорд: Oxford University Press. стр. 18. ISBN 9780199658855.
  11. ^ Фодор, JA (1986), «Проблема разума и тела», Scientific American , 244 (январь 1986)
  12. ^ Piccinini, Gualtiero (2015). Физические вычисления: механистический счет . Оксфорд: Oxford University Press. стр. 10. ISBN 9780199658855.
  13. ^ Giunti, Marco (1997). Вычисления, динамика и познание . Нью-Йорк: Oxford University Press. ISBN 978-0-19-509009-3.
  14. ^ Джунти, Марко (2017), «Что такое физическая реализация вычислительной системы?», Isonomia -- Epistemologica , 9 : 177–92, ISSN  2037-4348
Взято с "https://en.wikipedia.org/w/index.php?title=Вычисления&oldid=1251153053"