Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 2 down vote favorite

I'm preparing for an exam, and on a sample one provided (without solutions), we have this question: Is the following solvable or non-solvable: Given a turing machine $T$, does it accept a word of even length? - Given a deterministic 1-tape turing machine $T$, does $T$ ever read the contents of the 10th cell?

Thanks! -

share|improve this question
I think that they're both unsolvable by rice's theorem... but I am not sure if I can apply the theorem in both cases. What do you think? Would both of these constitute as "non-trivial properties"? What would be an example of a trivial property then? – Nizbel99 Dec 7 '12 at 22:11
Is the tape one side infinite, or two sided? In seems hard to avoid reading the 10th cell of a one sided infinite tape. – Hendrik Jan Dec 7 '12 at 22:23
It does not specify... Does it actually matter? – Nizbel99 Dec 7 '12 at 22:24
2  
It does matter: see the comment by Steve to the answer. Singe sided: then you have only a finite number of cells available, otherwise it is Turingcomplete if you avoid the 10th cell. Refer to the standard model you have been using in your lectures. Good luck with the exam... – Hendrik Jan Dec 8 '12 at 1:03
@HendrikJan: Also one has to be precise, what "reads the content of a cell" means. – A.Schulz Dec 8 '12 at 5:55
show 1 more comment

1 Answer

up vote 3 down vote

"Non-trivial properties" for Rice's theorem are properties of the language, not of the machine itself - for instance, it's decidable how many states a TM has, which is certainly a non-trivial property! See Perplexed by Rice's theorem for a bit of a clarification on this. Now, one of your two properties is a property of the language, while one is a property of the machine; this should allow you to apply Rice's theorem in one case but not the other. Note that this isn't conclusive evidence that the other case is solvable, but it's guidance that you might try looking for a positive answer there.

(Note that this is meant to be a very loose hint just to guide you; I can certainly go into more specific details if you'd like...)

share|improve this answer
Oh I see! I had missed this difference. So I can only apply Rice's theorem to the even length problem, while for the other one, given that it's asking about a property of the machine itself, I would have to conclude this using a different argument. Right? – Nizbel99 Dec 7 '12 at 22:26
1  
@Nizbel99 Precisely! (And as for an argument in the other case: Can you solve the halting problem for a 'Turing Machine' with a finite number of symbols and just 9 slots on its tape?) – Steven Stadnicki Dec 7 '12 at 22:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.