Правда ли, что существуют математические проблемы, которые в принципе нерешаемые?

Ответить
Ответить
Комментировать
0
Подписаться
2
2 ответа
Поделиться

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

Антон Климовотвечает на ваши вопросы в своейПрямой линии

Существует и таких проблем несчетное множество. 

Количество решаемых проблем бесконечно и счетно, а количество нерешаемых проблем бесконечно и несчетно.

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

Ответить