Уявіть, що у мене є властивість машини Тюрінга, яка виглядає приблизно так:
P = {M | L(M) is accepted by a Turing machine that does not halt in an even number of steps for any input}
Як я можу довести, що ця властивість тривіальна? Або, загалом, чи є хороші способи довести подібну річ?
Відповіді:
3 для відповіді № 1Як натяк: ви можете зробити будь-яку ТМ завжди зупинкою на непарній кількості кроків, зробивши дві копії станів - "непарну" копію і "парну" копію - і перемикаючись між ними вперед і назад, коли відбуваються переходи. Як тільки ви це зробили, як би ви модифікували цю машину, щоб вона ніколи не зупинялася через рівну кількість кроків? Враховуючи, що ця конструкція працює для будь-якої довільної ТМ, чи бачите ви, чому вищевказана властивість є тривіальною?
Сподіваюся, це допомагає!