Сообщение Re: Пофантазирем про хранение данных от 17.10.2016 15:31
Изменено 17.10.2016 15:33 kochetkov.vladimir
Здравствуйте, Voblin, Вы писали:
V>Понятно, что те задачи, которые прежде вообще не имели решения, станут обыденностью. Интересно, какие?
А с чего бы им становиться обыденностью?
Если речь об алгоритмическии-неразрешимых задачах (вычисление нетривиальных инвариантных свойств вычислимых функций -> проблема остановки / классификация алгоритмов / анализ кода / проблемы бобра-задрота и самоприменимости и т.п.), то они так и останутся неразрешимыми, поскольку тьюринговая модель вычислений изначально подразумевает бесконечную память и ничего нового эта коробочка здесь не принесёт.
Если же под задачами, не имеющими решения, подразумеваются задачи, решение которых упирается во всевозможные ограничения по памяти, то оних вполне себе решаются и сейчас, в рамках трейдоффа "время-память". Корбочка позволит решать PNSPACE задачи в квадрат быстрее, а NEXPSPACE — в экспоненту. Что, к слову сказать, прямо сейчас можно получить соответствующим увеличением производительности решателя, раз уж мы затронули тему грязных фантазий. Или применением для отдельных задач, в рамках квантовой модели, алгоритмов Гровера и Саймона, соответственно.
Короче, с точки зрения "нерешаемых задач" особой сенсации ждать не стоит.
V>Понятно, что те задачи, которые прежде вообще не имели решения, станут обыденностью. Интересно, какие?
А с чего бы им становиться обыденностью?
Если речь об алгоритмическии-неразрешимых задачах (вычисление нетривиальных инвариантных свойств вычислимых функций -> проблема остановки / классификация алгоритмов / анализ кода / проблемы бобра-задрота и самоприменимости и т.п.), то они так и останутся неразрешимыми, поскольку тьюринговая модель вычислений изначально подразумевает бесконечную память и ничего нового эта коробочка здесь не принесёт.
Если же под задачами, не имеющими решения, подразумеваются задачи, решение которых упирается во всевозможные ограничения по памяти, то оних вполне себе решаются и сейчас, в рамках трейдоффа "время-память". Корбочка позволит решать PNSPACE задачи в квадрат быстрее, а NEXPSPACE — в экспоненту. Что, к слову сказать, прямо сейчас можно получить соответствующим увеличением производительности решателя, раз уж мы затронули тему грязных фантазий. Или применением для отдельных задач, в рамках квантовой модели, алгоритмов Гровера и Саймона, соответственно.
Короче, с точки зрения "нерешаемых задач" особой сенсации ждать не стоит.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>
Re: Пофантазирем про хранение данных
Здравствуйте, Voblin, Вы писали:
V>Понятно, что те задачи, которые прежде вообще не имели решения, станут обыденностью. Интересно, какие?
А с чего бы им становиться обыденностью?
Если речь об алгоритмическии-неразрешимых задачах (вычисление нетривиальных инвариантных свойств вычислимых функций -> проблема остановки / классификация алгоритмов / анализ кода / проблемы бобра-задрота и самоприменимости и т.п.), то они так и останутся неразрешимыми, поскольку тьюринговая модель вычислений изначально подразумевает бесконечную память и ничего нового эта коробочка здесь не принесёт.
Если же под задачами, не имеющими решения, подразумеваются задачи, решение которых упирается во всевозможные ограничения по памяти, то они вполне себе решаются и сейчас, в рамках трейдоффа "время-память". Коробочка позволит решать NSPACE задачи в квадрат быстрее, а NEXPSPACE — в экспоненту. Что, к слову сказать, прямо сейчас можно получить соответствующим увеличением производительности решателя, раз уж мы затронули тему грязных фантазий. Или применением для отдельных задач, в рамках квантовой модели, алгоритмов Гровера и Саймона, соответственно.
Короче, с точки зрения "нерешаемых задач" особой сенсации ждать не стоит.
V>Понятно, что те задачи, которые прежде вообще не имели решения, станут обыденностью. Интересно, какие?
А с чего бы им становиться обыденностью?
Если речь об алгоритмическии-неразрешимых задачах (вычисление нетривиальных инвариантных свойств вычислимых функций -> проблема остановки / классификация алгоритмов / анализ кода / проблемы бобра-задрота и самоприменимости и т.п.), то они так и останутся неразрешимыми, поскольку тьюринговая модель вычислений изначально подразумевает бесконечную память и ничего нового эта коробочка здесь не принесёт.
Если же под задачами, не имеющими решения, подразумеваются задачи, решение которых упирается во всевозможные ограничения по памяти, то они вполне себе решаются и сейчас, в рамках трейдоффа "время-память". Коробочка позволит решать NSPACE задачи в квадрат быстрее, а NEXPSPACE — в экспоненту. Что, к слову сказать, прямо сейчас можно получить соответствующим увеличением производительности решателя, раз уж мы затронули тему грязных фантазий. Или применением для отдельных задач, в рамках квантовой модели, алгоритмов Гровера и Саймона, соответственно.
Короче, с точки зрения "нерешаемых задач" особой сенсации ждать не стоит.
... << RSDN@Home 1.0.0 alpha 5 rev. 0>>