From: Catalin Dima <cdima@inrialpes.fr>
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.