Я должен показать уменьшение: HALTING ≤ HALTING5, где HALTING (M, x) - это нормальная проблема остановки, но HALTING5 (M) = 1, если в программе M-Turing Machine существует не менее 5 различных x, для которыхМашина Тьюринга M останавливается
Я пытался показать сокращение следующим образом:
Мы берем такую функцию, что HALTING5 (M, w) и (M ', w'), где M - произвольныйобычный TM, w - строка над входным алфавитом M, M '- результат после остановки или операций, а w' - результат после проверки набора строк w = {x}, и M принимает w тогда и только тогда, когда M 'принимает W '.Для любого M пусть M '- DMTM, построенный в TM, и пусть w' = f (w), где f - функция и часть w.Теперь мы можем видеть, что поиск содержит три строки из-за большого количества остановок.И в нем есть только переменная M, количество остановок или остановок будет минимальным по сравнению с HALTING5.Это будет связано с большим количеством переменных, присутствующих в HALTING5 по сравнению с HALTING.
Я действительно не уверен, что это правильный способ показать сокращение, поэтому все предложения приветствуются!