L = {T | T是可识别{00，01}}的图灵机 [英] L = {T | T is a turing machine that recognizes {00, 01}} Prove L is undecidable

问题描述

L = {< T> | T是可识别{00，01}}

L = {<T> | T is a turing machine that recognizes {00, 01}}

证明L不确定.

我什至在理解要在此处使用减少量的过程中都遇到了困难.

I am really having difficulties even understanding the reduction to use here.

我不是要免费午餐，只是朝着正确的方向前进.

I'm not asking for free lunch, just a push in the right direction.

推荐答案

赖斯定理的直接应用将使您无需做任何工作即可证明这一点.

A direct application of Rice's theorem will let you prove this without doing any work at all.

某些图灵机识别出{00，01}.有些没有.区别在于语义，因为它与接受的字符串有关，而不与自动机的结构有关.因此，根据赖斯定理，该集合是不确定的.

Some Turing machines recognize {00, 01}. Some don't. The difference is semantic in that it has to do with the strings accepted, not the structure of the automaton. Hence, by Rice's theorem, this set is undecidable.

这篇关于L = {T | T是可识别{00，01}}的图灵机的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！