Как выглядят языки программирования, если каждая вычислимая вещь может быть выполнена за 1 секунду?

Question

Вдохновленный this question

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

Используйте свое воображение, как это возможно, например. он использует какой-то гиперпространственный континуум, чтобы автоматически распараллеливать что угодно, насколько это желательно, чтобы он мог рассчитать ответ на любой вычислимый вопрос, независимо от его сложности времени и количества фактических «логических шагов» за одну секунду.

Однако он может отвечать только на вычислимые вопросы за одну секунду ... так что я не стану «невозможной» машиной (по крайней мере, я так не думаю) ... Например, эта машина все равно не будет " чтобы решить проблему остановки.

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

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

Answer 1

Обратите внимание, что даже если проблема с остановкой не является вычислимой, «это останавливается в пределах N шагов на всех возможных входах с размером, меньшим, чем M»!

Таким образом, любой язык программирования станет чисто спецификацией. Все, что вам нужно сделать, это точно указать условия pre и post функции, и компилятор может реализовать самый быстрый код, который реализует вашу спецификацию.

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

Answer 2

Может быть, это будет выглядеть как псевдо-код чем «реальный» код. В конце концов, вам больше не нужно беспокоиться о каких-либо деталях реализации, потому что, что бы вы ни пошли, это будет достаточно быстро.

Answer 3

Возможно, это язык haskell-ish. Честно говоря, это мечта ввести код. Вы программируете «законы» своих типов, классов и функций, а затем освобождаете их. Это невероятно весело, мощно, и вы можете написать очень сжатый и элегантный код. Это похоже на искусство.

Answer 4

Ваша недооценка O (1). Это означает, что существует постоянная C> 0 такая, что время для вычисления проблемы ограничено этим.

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

Answer 5

SendMessage travelingSalesman "Just buy a ticket to the same city twice already. You'll spend much more money trying to solve this than you'll save by visiting Austin twice." 
SendMessage travelingSalesman "Wait, they built what kind of computer? Nevermind." 

Answer 6

Масштабируемость не будет проблемой. У нас были бы ИИ более умные, чем мы. Нам больше не нужно было программировать, и вместо этого ИИ выяснил бы наши намерения, прежде чем мы их осознаем.

Answer 7

Это не совсем логично. Если вещь занимает O (1) раз, то n раз будет занимать O (n) время, даже на квантовом компьютере. Невозможно, чтобы «все» занимало O (1) раз.

Например: Grover's algorithm, упомянутый в принятом ответе на вопрос, с которым вы связались, занимает O (n^1/2) время, чтобы найти элемент в базе данных из n элементов. И это не O (1).

Answer 8

SQL - такой язык - вы запрашиваете какой-то фрагмент данных, и вы его получите. Если вам не нужно беспокоиться о мельчайших деталях реализации db, это может быть даже забавно для программирования.

Answer 9

Объем памяти или скорость памяти или скорость процессора не определяют сложность времени и пространства алгоритма. Базовая математика делает это. Спросите, как выглядят языки программирования, если все можно было бы вычислить в O (1), это как спросить, как выглядят наши калькуляторы, если pi равно 3, а результаты всех квадратных корней - целые числа. Это действительно невозможно, и если это не так, это вряд ли будет очень полезно.

Теперь, спрашивая себя, что мы будем делать с бесконечной мощностью процесса и бесконечной памятью, может быть полезным упражнением. Нам все равно придется иметь дело со сложностью алгоритмов, но мы, вероятно, будем работать как-то иначе. Для этого я рекомендую The Hundred-Year Language.

Answer 10

Если все это будет сделано в течение одной секунды, то большинство языков, в конечном счете выглядеть, я называю это DWIM теории (то, что я имею в виду теорию):

Just do what I said (without any bugs this time) 

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

Answer 11

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