The Problem:
Let L1 = {Kod(M) | M is a TM and when started with a blank input tape, M
eventually writes a 1 somewhere on the tape } Prove that L1 is undecidable.
I have the following 2 TMs whcih I have proved are undecidable to help me prove the current problem is undecidable. I want to use the reduction method to do so.
Key:
- TM : turing machine
- w : input string for the TM
< kod(m) > : just means a binary encoding of a turing machine m being that TM.
Ltm = { < kod(m), w > | m is a TM and m accepts w } Lh = { < kod(m), w > | m is a TM and m halts on w }