Что именно вычисление?

20

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

Dictionary.comОпределения вычислений, вычислений, вычислений и вычислений являются круговыми, поэтому это не помогает.

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

Например, не означает ли это, что, скажем, взрыв бомбы - это вычисление, при котором вход - это загорание предохранителя, а выход - взрыв?

Итак, что же такое вычисления?

Kelmikra
источник
Это отличный, классический вопрос.
Ран Г.
Дубликат ?
Рафаэль
@ Рафаэль Насколько я знаю, вычисления! = Алгоритм. Возможно, выполнение алгоритма - это вычисление.
Кельмикра
Для меня «P вычислимо» == «Существует алгоритм, который решает P» (для P некоторая проблема). Это может быть результатом с моей точки зрения TCS, хотя.
Рафаэль
@Raphael Это спрашивает, что такое вычисление, а не то, что это означает для P быть вычисляемым.
Кельмикра

Ответы:

6

Возможно, проблема здесь в том, чтобы искать очень конкретное определение очень общего понятия. Я не вижу проблемы просмотра практически всего как вычисления. Хотя мы не думаем об этом, все, что мы делаем, можно выразить с точки зрения физики составных частей, вплоть до жужжания кварков. У нас такая же ситуация с вычислениями. Есть входы, выходы и процесс (все из которых могут быть тривиальными). Являются ли они интересными или полезными в качестве вычислений или моделей вычислений - это совсем другой вопрос.

Самое сильное рабочее определение, которое мы имеем, приходит через (сильный) тезис Черча-Тьюринга, в котором говорится, что каждая возможная физически реализуемая модель вычислений не более мощна, чем машина Тьюринга. Если вы верите, что это правда, то, хотя у нас может быть много способов выразить что-то, в конечном итоге мы можем свести каждое вычисление к машине Тьюринга, что дает определение вычисления как «все, что мы можем свести к машине Тьюринга».

В этой модели взрывающаяся бомба является вычислением. Он не является широко применимым (мы надеемся;)), но мы можем каким-то образом моделировать его с помощью машины Тьюринга (хотя здесь есть спор о природе вывода и эквивалентности с выводом ТМ). Это также не очень хорошая модель вычислений в целом, так как кажется маловероятным, что модель взрывающейся бомбы завершена по Тьюрингу.

Люк Мэтисон
источник
2
Скорее не по теме, но держу пари, что модель взрывающейся бомбы завершена! Взрывы могут вызвать другие взрывы, которые могут быть использованы для распространения сигналов и создания орбитальных ворот. Бомба b может быть установлена ​​на взрыв в определенное время через устройство, но соседняя бомба может отключить устройство, не вызывая взрыв b, что позволяет не-воротам.
Кельмикра
@ Kyth'Py1k, как ворота в домино? Я не думаю, что это будет полное излечение, потому что вы не можете зацикливаться бесконечно, поскольку «вычисления» всегда останавливаются в зависимости от размера машины / минного поля
фрик с трещоткой
1
@ratchetfreak Нет, если останки бомб не превращаются в новые бомбы с помощью наноботов в них, а затем перемещаются ...
Кельмикра
4

Это вопрос, который Тьюринг решил решить в своей знаменитой статье 1936 года « О вычислимых числах» с приложением к проблеме Entscheidungs , в которой он придумал (что стало известно как) модель машины Тьюринга. Смотрите, в частности, раздел 9.

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

Основное различие между общим представлением о вычислениях и вашим примером (взрывающаяся бомба) заключается в том, что вычисляется. Что вычисляется вашей взрывающейся бомбой? Другим отличием являются вычислительные средства, но можно представить себе механическое устройство, которое использует бомбы для вычисления чего-то более законного.

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

Юваль Фильмус
источник
Конечно, взрыв - это расчет. Он «вычисляет» именно унитарное преобразование, которое описывает взрыв. Кстати, много раз физики, с которыми я встречался, были «расстроены», когда вы говорите, что (скажем, некоторые квантовые врата вычисляют унитарный, а не развивают его, или соответствующим образом преобразуют физическую систему (« Врата берут ручку и бумагу и вычисляют унитарный "?) :)
Ран Г.
Я прочитал девятый раздел «О вычислимых числах с приложением к проблеме Entscheidungs», но, похоже, это не помогло. Хотя я не читал это очень тщательно, казалось, это закладывало основу для машин Тьюринга. Вы говорите, что вычисления - это что-то, что можно смоделировать как действие, выполняемое машиной Тьюринга? Если так, разве почти все не будет вычислением? Например, взрывы бомб могут быть смоделированы как машина Тьюринга так, чтобы положения, скорость и типы квантовых частиц окружающих частиц кодировались как двоичные.
Кельмикра
"Что вычисляется твоей взрывной бомбой?" Рассчитывается изменение состояний частиц, окружающих бомбу, согласно законам физики.
Кельмикра
«Другой вопрос заключается в том, применимы ли классические понятия вычислений к тому, что мы воспринимаем сегодня как вычисления, а именно, к двустороннему взаимодействию между компьютером и пользователем». Я не думаю, что это именно то, что считается вычислением. Считается, что автономные роботы выполняют вычисления, хотя им не нужно взаимодействовать с пользователями.
Кельмикра
Вот идея: вычисления - это процесс генерации результатов, чтобы помочь выводу, сделанному оптимизаторами (например, людьми и роботами). Как это?
Кельмикра
1

AВИксAx A xYВИксAИкс

Другие великие ответы в этой теме пытаются построить связь между этим отображением и методом его достижения. То есть они объясняют, что для «вычисления» выходных данных некоторого входа нам нужен систематический, четко определенный метод, который переводит нас от входа к его выходу . Хотя это правда, это не обязательно для определения вычислений. В самом деле, если вы встретите Джина, и каждый раз, когда вы даете им число они отвечают с , тогда они что-то вычисляют (даже если это отображение не является рекурсивным, и ни один компьютер не может его создать).х у х уИксИксYИксY

В этом очень широком способе просмотра вычислений любое физическое устройство является компьютером: оно передает физическую систему в момент времени (ее вход) в другую систему в момент времени (выход). Более того, это вычисление хорошо определено (т. Е. Может быть задано компактно, например, с помощью унитарных матриц). Если вы спроектируете устройство должным образом, оно может выполнить практически любые (рекурсивные) вычисления, которые вы пожелаете. (Скотт Ааронсон довольно много говорит о «Может ли природа вычислить проблемы», хотя его фокус в основном на NP-полных задачах, это очень важно для этой дискуссии).t = 1Tзнак равно0Tзнак равно1

Итог: любое отображение определяет вычисление. Любое «устройство», которое преобразует вход в соответствующий выход, выполняет («вычисляет») это конкретное вычисление.



(1) мы можем распространить обсуждение на эти типы вычислений, что будет иметь смысл, когда вы будете думать о функциях, которые не являются рекурсивными, но я предпочитаю не идти туда.

Ран Г.
источник
Проблема с этим определением заключается в том, что оно не соответствует тому, как на самом деле используется слово «вычисление». Считается, что ПК выполняют вычисления, а взрывчатка - нет.
Кельмикра
ИМХО, отображение - это то, чем не являются вычисления. Я думаю, что вы путаете синтаксис и семантику. Очевидно, вы понимаете отображение как отношение ввода-вывода, как бы оно ни было определено. Судя по всем моим книгам, это семантика. Вычисление - это средство, используемое для фактического получения выходных данных, соответствующих некоторым входным данным, через последовательность шагов. В то время как вы можете сказать, что любое вычисление определяет отображение (если только синтаксическое), я думаю, что неправильно считать, что отображение определяет вычисление, если вы тщательно не объясните, что вы входите в гиперкомпьютинг, который кажется немного вне вопроса.
Бабу
Я должен уточнить дух моего ответа (я понимаю, что это не так): само отображение не является вычислением. Процесс преобразования входного сигнала в выходной сигнал , является вычислением этого конкретного отображения (функция). Я пытался донести, что конкретный процесс является релевантным, любой такой процесс является вычислением (даже очень абстрактным, например, «оракулом»).
Ран Г.
1

Я не буду пытаться определить, что такое вычисления, что было сделано довольно хорошо Люком Мэтисоном и Ювалом Фильмусом.

Однако размышление о взрывающемся устройстве как о вычислении привело меня к важному побочному вопросу: если взрыв - это вычисление, то что он вычисляет? Кроме представления устройства после того, как оно взорвалось.

Я стремлюсь к тому, чтобы мы могли довольно точно определить, что мы считаем вычислением, и даже то, что можно рассматривать (придумать?) Как единое целое. Мы можем описать вычисление. Но можем ли мы сказать, что это за вычисления?

Вычисления, как это обычно определяется, являются чисто синтаксической игрой. Это игра физических структур, которые трансформируются в соответствии с точными правилами. Поскольку наш единственный инструмент (вплоть до стандартных преобразований) для представления физических структур - это, в конечном счете, строка символов, вычисление в конечном итоге определяется как некий вид формальных преобразований в строках символов. Это верно для машин Тьюринга, лямбда-исчисления, частично рекурсивных функций и других менее популярных моделей. Слово исчисление (как в лямбда-исчислении) на самом деле отражает эту точку зрения, так как в латинском языке исчисления - это маленькие камни, используемые для представления.

Но это не говорит о том, что означает присоединение к этому синтаксису, что он представляет. Вот то, что я мало понимаю, так как я не специалист по таким вопросам (так что дважды проверьте меня). Проблема покрыта теорией моделей .

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

Одно и то же вычисление, или, точнее, одно и то же описание вычисления, может фактически иметь много моделей, соответствующих очень разным объектам.

Например, алгоритм GCD описывает вычисления. Но это может быть интерпретировано на натуральных числах или на многочленах.

Это напоминает цитату Бертрана Рассела :

Математика может быть определена как предмет, в котором мы никогда не знаем, о чем говорим, и не является ли то, что мы говорим, правдой.

Ситуация почти такая же для вычислений. Это формальная игра, в которой ходы можно понимать по-разному. Но на самом деле существуют глубокие связи между математикой, формально определяемой аксиоматическими системами, и теорией вычислений.

Вычисления, алгоритмика были определены для решения математических задач, и многие современные концепции были придуманы логиками, которые пытались понять механизмы, которые позволяют нам доказывать теоремы, начиная с аксиом и применяя правила вывода.

Следовательно, чтобы вернуться к взрывному устройству, оно, безусловно, может быть истолковано как манипулирование представлением, то есть как расчет. Но обычно довольно сложно связать с ним какое-либо значение, кроме самого себя.

Однако это не всегда так или не было. Принцип аналоговых вычислений основан на идее, что для вычислений, которые связаны каким-то точным образом, можно использовать различные системы представления. Затем мы можем рассчитать с одной системой, чтобы иметь представление о том, что будет рассчитывать другая система (слишком громоздкая для реального использования, например, юниверс :)) в соответствующих настройках.

Babou
источник
0

Мне нравится отвечать на подобные вопросы о терминологии в этимологических терминах.

Итак, вычисление происходит от латинского слова compŭtus, которое буквально означает «вычисление».

На латинских языках, таких как французский, итальянский, испанский или португальский (среди прочих), эта этимология разделяется с "сказкой" (историей) на французском языке compte / conte на испанском языке cuenta / cuento на португальском языке conta / conto и т. Д.

Таким образом, вычислить - значит рассчитать и рассказать, как этот расчет был сделан.

Поэтому я бы сказал, что вычисления - это процесс использования математических и логических правил для обработки данной информации, поэтому новая значимая информация выводится из исходных данных, отслеживая, как эта новая информация была сгенерирована (процессор, память, ввод и т. Д.). Выходные данные являются основами)

Луис Сиира
источник
По-французски сказка «конт», «куенто» по-испански. В то время как «compte» является расчетом, или счет, «cuenta» на испанском языке. Я не знаю, что хотя гомофоны «compte» и «conte» имеют общую этимологию (нет «h» afaik), но эта общая этимология, кажется, подтверждается в сети. Так что весь этот вычислимый бизнес - это всего лишь сказки?
Бабу
Je l'ai corrigé. Я не должен
допускать
Или, может быть, сказки просто расчеты. Вы берете группу персонажей с заданной личностью в некоторых начальных условиях, и остальная часть истории вычисляется
Луис Сиира
«Отслеживание того, как эта новая информация была сгенерирована (процессор, память, ввод и вывод являются основными элементами)». Разве это не влечет за собой то, что что-то не является вычислением, если при этом не следить за использованием их памяти? Это звучит неправильно ...
Кельмикра