Would a "TM starting with a blank tape will ever write a nonblank symbol anywhere before halting" be undecidable?

  • 2
    $\begingroup$ What are your thoughts? What progress have you made? This site works a bit differently from others you might be used to: we expect you to try to solve it on your own before asking here. We're not a "homework help site". We're happy to help you understand the concepts but just solving exercise-style tasks for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$
    – D.W.
    May 6 at 22:55
  • $\begingroup$ I think it is undecidable because it is both a blank tape and halting problems. And I know both of these problems are undecidable, but I am unsure if I am thinking in the right direction. $\endgroup$
    – Lunar
    May 7 at 0:04
  • 2
    $\begingroup$ The way to know that something is undecidable is to prove it, by showing a reduction. The way to know that smething is decidable is to prove it, by showing an algorithm that always terminates (a decider). Don't just guess, or try to assume patterns (e.g. assuming that if it involves a blank tape it is undecidable) -- prove your answer. The process of trying to prove your guess correct is an essential part of trying to solve these problems. Sometimes when you try to prove something, it gives you some additional insights and then you realize you need to adjust your guess. $\endgroup$
    – D.W.
    May 7 at 1:49
  • 1
    $\begingroup$ How many machine states are there to consider? (I removed one word from that question.) $\endgroup$
    – greybeard
    May 7 at 4:21
  • $\begingroup$ We can start by considering just 2 machine states, an initial and final state. $\endgroup$
    – Lunar
    May 7 at 4:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.