математика - Машина Тьюринга и его возможности

Помните ещё меня? Я тот кто так яро пытался решить проблему равенства P и NP. Я близок к тому, чтобы решить задачу о рюкзаке P-задачами, осталось скомпоновать это в более подобающий вид.

@DarKProGameR: я потом посмотрел предыдущие вопросы и вспомнил.

учебник по теории алгоритмов Вам в помощь

я вас понял

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

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

@falcao Так что мне сейчас делать? Показать свои решения в удобном виде, чтобы потом обсудить с вами что делать дальше?

@falcao тогда можете сказать, можно ли узнать все ли решения при любых входных данных могут быть оптимальны или тут только сидеть и решать примеры с разными входными данными? И если всё-таки придется ручным образом решать множество примеров, можно ли будет предоставить это какому-нибудь языку программирования?

@falcao да, действовать как машина Тьюринга программа будет, но объем памяти компьютера и программы ограничен, а у машины Тьюринга нет. Формально, машиной Тьюринга компьютерная программа являться не будет. Хотя для конкретной МТ с ограниченным объемом памяти программу на компьютере написать, конечно, можно. Тут я несколько неверно выразился про соответствие.

@DarKProGameR как я понимаю, вы хотите провести доказательство корректности алгоритма. Зачастую это можно сделать в общем виде, но не зная самого алгоритма, помочь ничем нельзя.

@True_Romance может стоить закодить программу для генерации случайных переменных разного количества, а потом просто сверить с решениями неполиномиального алгоритма?

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

@True_Romance тогда что делать?

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

@True_Romance мне бы сначала скомпоновать в более читаемый вид, а то пока всё только в черновиках

У меня назрел вопрос, насколько мощными станут компьютеры, если равенство P=NP будет доказано?