From: Catalin Dima Subject: Re: printing problem (similar to Halting problem...I think) Date: Wed, 29 Mar 2000 09:55:59 +0000 Newsgroups: sci.math Summary: [missing] > please redirect me if there is a more appropriate forum for this question, I > am new to math of this sort ( I dont even know what sort it is properly) > You should have posted this problem to comp.theory newsgroup. > > Could someone guide me on how to mathematically express this problem > (Printing Problem): > > Given an arbitrary Turing machine Z, an initial input tape t, and symbol S, > decide if Z will ever print the symbol S during the course of a computation > starting with t on its input tape. Hint: modify each Turing machine such that it prints a special symbol _just after_ it stops (or better said, just after the old machine would have stopped). Then use the classical proof-by-contradiction technique: if this problem were decidable, then the halting problem would have been decidable too. Of course, pay attention to the details and practice this technique on other undecidability problems ;-) it worths mastering since it's _the_ technique in proving any undecidability result. Cheers, Catalin.