-1

Каковы возможности машины Тьюринга? Какие математические или логические операции он может совершать?

задан 7 Мар 20:46

2

"Он" -- это машина, или сам Тьюринг? :)

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

(7 Мар 21:24) falcao

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

(7 Мар 21:52) DarKProGameR
1

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

(7 Мар 22:38) falcao
1

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

(7 Мар 22:42) haosfortum

я вас понял

(7 Мар 23:26) DarKProGameR
1

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

(8 Мар 3:32) Казвертеночка
1

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

(8 Мар 16:38) True_Romance
2

@True_Romance: не понял Вашей мысли. То и другое способно выполнять любые алгоритмические действия. На компьютере легко создать устройство, которое действует как машина Тьюринга.

(8 Мар 16:43) falcao

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

(8 Мар 16:50) DarKProGameR
2

@DarKProGameR: почему Вы спрашиваете меня, что Вам делать? Я если и мог бы ответить на какие-то вопросы, но в лучшем случае математического содержания.

(8 Мар 16:55) falcao

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

(8 Мар 17:01) DarKProGameR
1

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

(8 Мар 17:44) True_Romance
1

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

(8 Мар 17:46) True_Romance

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

(8 Мар 18:09) DarKProGameR
2

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

Лондон. Утро. Старый лорд в спальном халате спускается в гостиную, подходит к высокому окну. Дворецкий раздвигает шторы. Лорд смотрит на утренний туман и произносит: - Сегодня смог! Дворецкий, почтительно склонив голову, произносит: - Поздравляю, сэр!

(8 Мар 18:17) Казвертеночка
1

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

(8 Мар 18:20) True_Romance

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

(8 Мар 18:30) DarKProGameR
1

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

(8 Мар 18:37) True_Romance

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

(8 Мар 18:43) DarKProGameR

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

(8 Мар 19:42) DarKProGameR
2

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

(8 Мар 19:50) True_Romance
показано 5 из 21 показать еще 16
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×4,001
×1,108
×500
×66
×36

задан
7 Мар 20:46

показан
155 раз

обновлен
8 Мар 19:51

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru