Oracle machine

[BormoGlott]

А смогла бы такая машина выиграть в шахматы у другой такой же машины? или обе перегорели бы как те роботы в фильме "Москва – Кассиопея"

[_Swetlana]

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

Это что за зверь такой?

Любая подпрограмма, которая занимается только вычислениями, но не вводом-выводом.

Так, мой юный друг  Все мы не без дефекта, и у меня тоже есть (профессиональная) деформация личности, так что я тут вам лекцию прочитаю 
Вычислимая функция - это функция, вычислимая по Тьюрингу или по Чёрчу.
Более подробно, есть Тезис Тьюринга (по сути, определение или математическая модель алгоритма): Любой алгоритм может быть вычислен на ДМТ (детерминированной машине Тьюринга).
Есть Тезис Чёрча, что любая вычислимая фукнция - это частично-рекурсивная функция.
Затем доказывается теорема, что две эти модели эквивалентны, то есть что вычислимо по Тьюрингу, то вычислимо по Чёрчу и наоборот.
Далее. Следите за моими руками рассуждениями 

1. Если говорить совсем уж детским языком, то вычислима та функция, для (точного) вычисления которой можно написать программу.
2. Вычислимых функций ровно столько, сколько вы, мой юный друг, теоретически сможете написать программ за бесконечное время.
3. Эти программы можно будет пронумеровать 1,2, 3 ... то есть таких программ, соответственно, вычислимых функций счётное количество.
Точно мы можем вычислить с помощью чего угодно за бесконечное время только счётное количество функций.
4. Только функций вида f: N->N несчётное количество. Этот факт легко доказывается. Берём любое вещественное число, вернее, его запись в виде десятичной дроби и нумеруем цифры в записи. Теперь строим функцию f так: f(i)=record(i), где  record(i) - i-я цифра в десятичной записи выбранного числа.
Действительные числа различны и их несчётно, соответственно, мы таки имеем несчётное количество функций.
Всего функций несчётно, а вычислимых функций счётно.
5. Невычислимых функций несчётно, и никакой суперкомпьютер этому горю не поможет.
Рыдаем, чо   

[Upliner]

А в чём горе-то?

[_Swetlana]

А в чём горе-то?

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

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

[Upliner]

Я вообще-то изначально не обозначал никаких задач, что имеется в виду?

[_Swetlana]

Я вообще-то изначально не обозначал никаких задач, что имеется в виду?

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

[Upliner]

Суперкомпьютер описал, да, а вот задачи ему ставить предложил прочим участникам. Ну и для примера число Грэма привёл.

[_Swetlana]

Вот не знаю, чего я привязалась к такой безобидной теме. Если ты мечтаешь тоже, то мечтай, а как же быть 
Но всё же.
Единственная проблема с вычислениями (других нет) - проблема экспоненциальных вычислений. Система из n элементов имеет 2ⁿ состояний, которое для нас слишком велико, для n>=20.
И эту проблему собираются решить квантовыми вычислениями (квантовым компьютером). Но в этом я ничего не понимаю.

[Easyskanker]

"Квантовый" в наше время это такая респектабельная замена слову "волшебный".

[_Swetlana]

"Квантовый" в наше время это такая респектабельная замена слову "волшебный".

Не думаю. Идею квантового компьютера предложил Юрий Манин, человек серьёзный и известный математик. Я в этом ничего не понимаю, что косвенно подтверждает ценность теории  Насколько эта идея может быть реализована в виде физического устройства - тоже не могу сказать. Может, время ещё не пришло.
Вначале Тьюринг придумал тер. основы, потом появились ЭВМ.

[Mass]

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

[_Swetlana]

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

А толку-то. Ну и попадёт на предыдущий уровень рекурсии. Бесконечная рекурсия, однако.

[Mass]

А толку-то. Ну и попадёт на предыдущий уровень рекурсии. Бесконечная рекурсия, однако.

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

[_Swetlana]

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

[Upliner]

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

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

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

Вот такой возможности нет.

[Mass]

Вот такой возможности нет.

В вашей фэнтези-вселенной вместо бэка - рояль и кактус 

[Upliner]

Вот такой возможности нет.

В вашей фэнтези-вселенной вместо бэка - рояль и кактус 

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

[Upliner]

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

Ну а если какому-то математику для каких-то теоретических построений позарез нужно будет точно знать жалкие 1000 цифр десятичного представления числа Грэма начиная с цифры под номером гуголплекс?

[Mass]

А толку-то. Ну и попадёт на предыдущий уровень рекурсии. Бесконечная рекурсия, однако.

А ё ж. Кажется, Вы меня неправильно поняли.

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

Т.е. для нас тогда некоторая задача со временем решения 10³⁵ лет решается за сотую долю секунды, сам же компьютер проводит все эти 10³⁵ лет в сей временной петле.

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

Всё равно обязательное дело, ИМХО. Просто бесценная фича была бы...

[Mass]

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

Это какой? Сценарий можете дать?

[Upliner]

Это какой? Сценарий можете дать?

Завсисит от способа перемещения в прошое и ограничений(может переместиться до момента создания/включения?)

[_Swetlana]

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

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

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

Вот такой возможности нет.

Не обижайтесь, а послушайте  Кому что надо и куда надо выйти.
250 слябов - суточный портфель заказов листопрокатного цеха (за сутки прокатывают 250 слитков металла). Из них диспетчер каждый день составляет упорядоченную последовательность. Размерность пространства поиска (число возможных планов) равна 250!
Если через число Авогадро посчитать количество атомов в видимой нами части Вселенной, то оно будет немного меньше 250!
А это всего лишь суточный портфель заказов, горизонт планирования - сутки, через 5 минут должен быть составлен план (требование к программному продукту).

[Mass]

Завсисит от способа перемещения в прошое и ограничений(может переместиться до момента создания/включения?)

Не может ни то ни другое.

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

[Upliner]

Не может ни то ни другое.

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

Тогда не понимаю в чём смысл. Или это просто предлагаемая схема реализации предлагаемой машины?

[Mass]

Или это просто предлагаемая схема реализации предлагаемой машины?

Таки да. Вы против?