- #1
WWCY
- 479
- 12
- Homework Statement
- I need help deciding whether or not the following tasks are undecidable (problems 1c, 1d and 1e).
I have attempted solutions but am very unsure if they are right.
- Relevant Equations
- Definition of blackbox property: A property P(T) (where T is a Turing machine) is a blackbox property iff P(T) = P(T') for all T,T' such that they halt on the same inputs x and on the inputs they halt, T(x) = T'(x).
Rice's theorem: Any non-trivial blackbox property is undecidable
I should first note that I am not a compsci student, and have not learned the "formal" way of using "Languages" to solve such problems. All I have are the two definitions provided above. Thanks!
1b) This is the Halting problem: Undecidable
1c) I have a feeling that this is decidable, since if you peer into any given Turing machine you'd be able to count the timesteps?
1d) I think this is undecidable; suppose ##\exists \ \text{Turing} \ H## that outputs ##1## if ##T,T'## both return ##24## on the same inputs ##x## and ##0## otherwise. If I design the valid Turings ##T,T'## that look like ##\text{function} \ T(x) \rightarrow \ \text{Execute} \ M(x) \rightarrow \ \text{return} \ 24## for arbitrarily chosen Turing ##M##, then ##H(T,T') = 1##. However, ##H = 1 \ \text{iff} \ T,T'## both return ## 24 \ \text{iff}## both ##M,M'## halt on arbitrary ##x##. This means such ##H## can solve the Halting problem and we have a contradiction; there cannot be such ##H##.
1e) The property ##P(G):=## "Will this game ##G## with input ##x## have live cells outside a given area" seems to be a blackbox property; Any two games ##G## and ##G'## with the same input ##x## will surely give the same output as the rules are deterministic. This is also non-trivial as ##P## may differ from input to input. So by Rice's theorem it is uncomputable?
Thanks in advance for any assistance
1b) This is the Halting problem: Undecidable
1c) I have a feeling that this is decidable, since if you peer into any given Turing machine you'd be able to count the timesteps?
1d) I think this is undecidable; suppose ##\exists \ \text{Turing} \ H## that outputs ##1## if ##T,T'## both return ##24## on the same inputs ##x## and ##0## otherwise. If I design the valid Turings ##T,T'## that look like ##\text{function} \ T(x) \rightarrow \ \text{Execute} \ M(x) \rightarrow \ \text{return} \ 24## for arbitrarily chosen Turing ##M##, then ##H(T,T') = 1##. However, ##H = 1 \ \text{iff} \ T,T'## both return ## 24 \ \text{iff}## both ##M,M'## halt on arbitrary ##x##. This means such ##H## can solve the Halting problem and we have a contradiction; there cannot be such ##H##.
1e) The property ##P(G):=## "Will this game ##G## with input ##x## have live cells outside a given area" seems to be a blackbox property; Any two games ##G## and ##G'## with the same input ##x## will surely give the same output as the rules are deterministic. This is also non-trivial as ##P## may differ from input to input. So by Rice's theorem it is uncomputable?
Thanks in advance for any assistance