Наука, финансирование, прорывные открытия — почему их так мало сейчас

Sandro> А Алан Тьюринг обосновал, что для неё можно написать программу, какую хочешь.

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

16-й> Вроде ж не "можно написать", а что где-то там, в бесконечном множестве бинарного кода произвольной длины, существует эта самая программа. Что, как мне кажется, не одно и то же.

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

16-й>> Вроде ж не "можно написать", а что где-то там, в бесконечном множестве бинарного кода произвольной длины, существует эта самая программа. Что, как мне кажется, не одно и то же.
Zenitchik> Нет. Именно, что можно реализовать любой алгоритм. Полнота по Тьюрингу.

Ну, то я криво выразился. Понятно, что если такая последовательность кода в принципе существует, то можно ее реализовать. Опять же в принципе. Но в практическом смысле это мало что дает.
Вообще, некое недоумение от машины Тьюринга у меня осталось еще со студенческих времен. Тем более, что нам ее давали без объяснения, на кой она понадобилась самому Тьюрингу. А он, как я позже узнал, хотел "переформулировать" теорему Геделя. Т.е. решал чисто математическую задачу, имеющую к программированию (в курсе которого она появилась у нас) весьма странное отношение.
Что характерно, я потом спрашивал разных коллег-программеров, что они думают про машину Тьюринга - все как один отвечали в духе "непонятно на кой черт она вообще нужна".

Zenitchik> ...состоящей только из элементов ИЛИ-НЕ. Там ничего сложного, громоздко только.

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

del

16-й> Вообще, некое недоумение от машины Тьюринга у меня осталось еще со студенческих времен. Тем более, что нам ее давали без объяснения, на кой она понадобилась самому Тьюрингу. А он, как я позже узнал, хотел "переформулировать" теорему Геделя. Т.е. решал чисто математическую задачу, имеющую к программированию (в курсе которого она появилась у нас) весьма странное отношение.
16-й> Что характерно, я потом спрашивал разных коллег-программеров, что они думают про машину Тьюринга - все как один отвечали в духе "непонятно на кой черт она вообще нужна".

Меня программированию не учили, сам нахватался. Поэтому об ихней теорией только что-то слышал. Но один мой коллега говорил, что через машину Тьюринга доказывается что-то, что потом применяется в доказательном программировании (он ещё хвастался, что багу в Линуксе таким образом нашёл и коммит им туда отправил). Я так понял, что практически полезные машины - слишком сложно математически описываются. А для доказательства каких-нибудь теорем по алгоритмике нужна очень просто устроенная абстрактная машина, и то, что интерпретируемый ей язык чертовски неудобен, в данном контексте не роляет.

>и-не / или-не можно построить все прочие "элементарные" булевы функции

Ага. А ещё триггер. А больше ничего и не нужно.

Zenitchik>> Нет. Именно, что можно реализовать любой алгоритм. Полнота по Тьюрингу.
16-й> Ну, то я криво выразился. Понятно, что если такая последовательность кода в принципе существует, то можно ее реализовать. Опять же в принципе. Но в практическом смысле это мало что дает.

Искать чёрную кошку в тёмной комнате, может быть много труднее, если даже не знаешь есть ли она там

16-й>> Ну, то я криво выразился. Понятно, что если такая последовательность кода в принципе существует, то можно ее реализовать. Опять же в принципе. Но в практическом смысле это мало что дает.
Ronin> Искать чёрную кошку в тёмной комнате, может быть много труднее, если даже не знаешь есть ли она там

Кошку обычно ищут согласно ТЗ. При этом по фигу есть она там или нет. А если само ТЗ велит искать кошку, то тем более.

Zenitchik> Я так понял, что практически полезные машины - слишком сложно математически описываются. А для доказательства каких-нибудь теорем по алгоритмике нужна очень просто устроенная абстрактная машина, и то, что интерпретируемый ей язык чертовски неудобен, в данном контексте не роляет.
Именно так.
Тут важно то, что машина удобна (некоторые говорят, что на самом деле - нет, но менять что-то поздновато уже) для математических доказательств.

Zenitchik> Меня программированию не учили, сам нахватался. Поэтому об ихней теорией только что-то слышал. Но один мой коллега говорил, что через машину Тьюринга доказывается что-то, что потом применяется в доказательном программировании (он ещё хвастался, что багу в Линуксе таким образом нашёл и коммит им туда отправил).

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

Sandro> Да, архитектурно она страшненькая, собственно, не зря её эмулятор называется brainfuck.

Брейнфак - это не эмулятор Машины Тьюринга. Принципиально другой язык и другая машина. Объединяет их только то, что они оба из т.наз. "Тьюрингова болота". С машиной Поста есть некоторая аналогия...

Sandro> любая программа для машины Тьюринга исполнима на любой цифровой машине с достаточной памятью.

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

А по существу поста согласен. Что можно сформулировать в виде таблицы переходов машины Тьюригна - выразимо на любом тьюринг-полном языке.

Sandro> ...и вот что важно: любая программа для машины Тьюринга исполнима на любой цифровой машине с достаточной памятью. То есть, если программа работает на ней, то она будет работать везде.

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

Sandro>> ...и вот что важно: любая программа для машины Тьюринга исполнима на любой цифровой машине с достаточной памятью. То есть, если программа работает на ней, то она будет работать везде.
16-й> Непонятно, почему это важно.

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

16-й> Вроде как сам Тьюринг и доказал, что проблема остановки его машины неразрешима аналитически.

Не, с остановимостью не к нему.

16-й> Т.е. чтобы что-то там доказать про исполнимость, надо сначала забабахать весь код алгоритма на этом страшно неудобном эмуляторе, отладить каким-то мозголомным способом, затем дождаться его окончания (крайне не оптимизированного), и только после этого что-то прояснится.
16-й> Какой в этом практический смысл?

А вот и нет, опять же. См теорию обобщенных функций. Когда мы обращаемся с функциями, как с числами. Ну, приблизительно.
Так вот: в общем случае: естественно, фиг докажешь. В частном — интересны случаи, когда вычислимость возможна. И вот тут есть пригодные алгоритмы, которые дают результат за приемлемое время. Ну или говорят "не шмогла".

16-й> Непонятно, почему это важно.

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

Zenitchik> Потому что это точка отсчёта. Позволяет ввести понятие Тьюринг-полного языка и критерии для определения полноты по Тьюрингу.

Звучит, конечно, громко.
"Полнота по Тьюрингу — характеристика исполнителя (множества вычисляющих элементов) в теории вычислимости, означающая возможность реализовать на нём любую вычислимую функцию."
Могу я на своем телефоне эмулировать машину Тьюринга, за исключением бесконечной ленты памяти? Могу. Все. У меня в телефоне полнота по Тьюрингу.
И? Легче мне стало?

Zenitchik> На Тьюринг-полном языке можно реализовать любой алгоритм (то, что Тьюринг называет алгоритмом). На неполном - нелюбой.

То же самое. Поди, заморишься искать язык, не "Тьюринг-полный". Ибо сложно представить что-то более примитивное.
Опять же, и? Что это дает?

16-й> То же самое. Поди, заморишься искать язык, не "Тьюринг-полный". Ибо сложно представить что-то более примитивное.
16-й> Опять же, и? Что это дает?
Например, язык без безусловного перехода (не позволяющий организовать бесконечные циклы) - не тюринг-полный.
Язык или машина без произвольного доступа к памяти - не тюринг-полные. Например, нельзя реализовать чисто стековую машину, к которой было бы применимо всё, что применимо к машине Тюринга.
Тюринг-полная машина должна позволять, например, неограниченное чтение (или запись) ячейки памяти (и это уже имеет практический смысл).
Там по мелочи набегает.

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

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

Расшифруй, плиз. Имеется ввиду "натуральный" генератор, на рулетке какой-нибудь, не эмулируемый программно?

Татарин>> Например, доказано, что машина с генератором случайных чисел принципиально мощнее машины без такого генератора, и, соотвественно, принципиально же незаменима.
16-й> Расшифруй, плиз. Имеется ввиду "натуральный" генератор, на рулетке какой-нибудь, не эмулируемый программно?
Да.

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

...
Ну или другой пример, более интересный: из этой возни с машиной Тюринга вылез тезис Чёрча-Тюринга, который гласит, что вне зависимости от деталей реализации, ЛЮБАЯ тюринг-совместимая машина даёт по отношению к ней максимум полиномиальный выигрыш (или проигрыш) на любом же алгоритме.
То есть, вот как биты или триты не тасуй, какой многозначной логикой ни пользуйся, как аппаратуру ни организуй, всё равно выигрыш полиномиальный (что сразу и принципиально ограничивает в решении NP-полных задач).

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

Татарин> Это сподвигло на поиски машины, выходящей за рамки машины Тюринга и этого тезиса. И, соотвественно, появление самой идеи квантовых вычислений, где рост мощности зависит как exp(размерности_когерентной_транзакции).

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

Татарин>> Это сподвигло на поиски машины, выходящей за рамки машины Тюринга и этого тезиса. И, соотвественно, появление самой идеи квантовых вычислений, где рост мощности зависит как exp(размерности_когерентной_транзакции).
16-й> А вот интересно, квантовый компьютер можно ли трактовать как "компьютер" в широком смысле слова, или это все-таки "переферийное устройство", в принципе обеспечивающее только какой-то узкий круг дополнительных вычислений?
Сейчас на практике это ускоритель для некоторых операций (более того, конкретных алгоритмов, которых, по сути два - квантовое Фурье и следующий из него Шор и Гровер).
В теории (вот той самой математическо-сфероконической) КК - это нормальный тюринг-совместимый вычислитель, который может делать всё то же, что и классический (при том, что обратное, ессно, неверно).
Не думаю, что в любом обозримом будущем КК сможет заменить классическую цифру.

16-й>Так если посмотреть, аналоговые "компьютеры", т.е. устройства, позволяющие реализовать несколько "программ", известны давно.
КК - не просто аналоговый комп. Он аналоговый, да, но это узкий подкласс, который позволяет решать NP-полные задачи за полиномиальное время.

16-й> Т.е. есть ли какая-то теория, которая четко очерчивает нишу для квантовых вычислений?
"Чётко" - нет, хотя бы уж потому, что квантовая система может делать всё, что классическая, потому что в некотором пределе к ней сводится. И вообще, квантовая механика в пределе сводится к классике.

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

16-й> Поди, заморишься искать язык, не "Тьюринг-полный".

Да их до жопы. Я сам парочку придумал под спецзадачи.

Татарин>> Вот можешь привести пример чего-то эквивалентного топологии - нового класса матобъектов, открывающего новый раздел математики?
Sandro> Пропустил это сообщение, сейчас попалось.
Sandro> Могу из теории цифровой техники привести. Штрих Шеффера, в первую очередь. Это фундаментальный результат.

Почему, к примеру, штрих Шефера, а не стрелка Пирса? Чем одно фундаментальнее другого?

Ну и что тут вообще нового? Оба этих базиса в матлогике как бы не старше топологии, им больше века - штрих 1913 год, стрелка (не в смысле осциллографа) - вообще 1880.

Sandro> Он доказывает, что любую цифровую вычислительную машину можно построить на основе всего лишь одного элемента. 2И-НЕ, или 2ИЛИ-НЕ. Неважно. Берём ящик 7400, ну или 155ЛА3, и начинаем паять.

Но только, пардон, что тут фундаментального и нового (или фундаментально нового) с точки зрения именно чистой математики?

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

Fakir> НЕОГРАНИЧЕННОЕ НАУЧНО-ТЕХНИЧЕСКОЕ РАЗВИТИЕ И ЕГО ФУНДАМЕНТАЛЬНЫЕ ПРЕДЕЛЫ

Но это же статья 2014 года? Или другая с тем же названием?

PS: Сейчас перечитал статью 2014 года. Набор букв, написанный гуманитарием. Как она попала ... а ааа ааааа блин ....

"НАУЧНО-МЕТОДИЧЕСКИЙ ЖУРНАЛ
XXI век: итоги прошлого
и проблемы настоящего плюс
Периодическое научное издание
Серия: социально-гуманитарные науки
04(20)/2014"