Приведите простые примеры

задан 15 Фев '12 21:06

что вы подразумеваете под термином "невычислимая"?

(15 Фев '12 21:57) Hedgehog

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

(12 Мар '12 22:06) asianirish
10|600 символов нужно символов осталось
3

Так как нормально вычислимых функций счётное множество, то перенумеруем все эти функции. Таким образом, всякая нормальная функция имеет некоторый номер. Пусть P0, P1, P2 ... - все нормально вычислимые функции. Определим функцию f следующим образом:
f(x) = {Px(x)+1, если Px(x) определено; 1, если Px(x) не определено.

Если предположить, что функция f(x) нормально вычислима, то получим, что f(x) = Pk(x) для некоторого k из множества N0 (натуральные и 0). Так как f(x) всюду определена, то и Pk(x) определена всюду на N0.

Тогда f(k) = Pk(k). Но по опрeделению функции f(x) имеем: f(k) = Pk(k)+1.
Из двух последних равенств получаем противоречивое равенство: Pk(k) = Pk(k)+1.
Таким образом, определённая выше функция f(x) не является нормально вычислимой. И потому не является вычислимой по Тьюрингу и частично рекурсивной, то есть для вычисления всех её значений не существует алгоритма.


Взято отсюда: Дискретная математика. Кулабухов С.Ю, страница 143.

ссылка

отвечен 15 Фев '12 22:09

изменен 16 Фев '12 21:42

%D0%A5%D1%8D%D1%88%D0%9A%D0%BE%D0%B4's gravatar image


5525

10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×471

задан
15 Фев '12 21:06

показан
2431 раз

обновлен
12 Мар '12 22:18

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

по почте:

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

по RSS:

Ответы

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

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