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

Question

Вдохновлен этим вопросом

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

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

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

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

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

Answer 1

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

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

Answer 2

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 3

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

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

Answer 4

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

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

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

Answer 5

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

Answer 6

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

Answer 7

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

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

Answer 8

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

Answer 9

Я не знаю, какие новые языки появятся (я физик, а не специалист по информатике), но я все еще писал бы свои программы для этого на Python.

Answer 10

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

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

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