Медведевская сводимость

В теории вычислимости множество P функций $\mathbb {N} \rightarrow \mathbb {N}$ называется сводимым по Медведеву к другому множеству Q функций $\mathbb {N} \rightarrow \mathbb {N}$ когда существует оракул-машина Тьюринга , которая вычисляет некоторую функцию от P задается некоторая функция из Q. всякий раз, когда ей в качестве оракула ^[1]

Сводимость Медведева — это универсальный вариант сводимости Мучника , требующий единой машины-оракула, которая может вычислить некоторую функцию от по любому оракулу из Q , вместо семейства машин-оракулов, по одной на каждый оракул из Q , которые вычисляют функции из P. P ^[2]

См. также

Ссылки

^ Хинман, Питер Г. (2012). «Обзор степеней Мучника и Медведева» . Бюллетень символической логики . 18 (2): 161–229. дои : 10.2178/bsl/1333560805 . JSTOR 41494559 .
^ Симпсон, Стивен Г. «Массовые проблемы и степени неразрешимости» (PDF) . Проверено 10 июня 2024 г.

Эта математической логике статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее .

[hinman-1] Хинман, Питер Г. (2012). «Обзор степеней Мучника и Медведева» . Бюллетень символической логики . 18 (2): 161–229. дои : 10.2178/bsl/1333560805 . JSTOR 41494559 .

[simpson-2] Симпсон, Стивен Г. «Массовые проблемы и степени неразрешимости» (PDF) . Проверено 10 июня 2024 г.

[1]

[2]