3
$\begingroup$

Let

$$ L_{300}=\{\langle M,w\rangle \mid M\text{ prints more than }300\text{ non-blanks on input }w\}.$$

Is $L_{300}$ decidable?

My intuition is it is decidable because given $M$ and $w$, we need to check for a bounded number of steps which would be a function of the number of states in the finite automata of $M$, input alphabet and the length of the input $w$. Can someone give an intuition for getting the exact bound or tell if its undecidable ?

$\endgroup$
  • 1
    $\begingroup$ Why do you think you only need to check a bounded number of steps? $\endgroup$ – David Richerby Sep 19 '18 at 11:32
  • $\begingroup$ @DavidRicherby Firstly because I couldn't find a suitable way of reducing any undecidable problem to it and felt it should be decidable. Secondly, my intuition was it can only write blanks or just read, so if we check for finite steps and it doesn't write non-blanks in those number of steps, we dont have to check for more because the same thing will repeat. $\endgroup$ – Arka Pal Sep 19 '18 at 12:01
  • 2
    $\begingroup$ (a) What are some of the undecidable problems you tried? (b) what if 300 is replaced with 0, or 1, or 10 -- any change/thoughts? $\endgroup$ – usul Sep 19 '18 at 17:14
  • $\begingroup$ If $M$ prints a non-blank then prints a blank at the same position, does it count as one non-blank? $\endgroup$ – xskxzr Sep 20 '18 at 9:49
  • $\begingroup$ @xskxzr yes it counts as one non-blank simply because one non-blank is printed, blanks dont count. $\endgroup$ – Arka Pal Sep 20 '18 at 16:48
1
$\begingroup$

It is decidable. The decider $D$ is described as the following pseudocode by Church–Turing thesis. The syntax of the pseudocode is borrowed from Python.

configurations = [the initial confituration]
print_non_blank = []
min = 0
max = len(w) - 1
while M does not halt on w:
    simulate one step of M on w
    configuration = the current configuration
    if M prints a non-blank:
        print_non_blank.append(1)
        if sum(print_non_blank) > 300: # Check 1
            return ACCEPT

        # update the non-blank area
        p = the position where M prints the non-blank
        if p > max:
            max = p
        if p < min:
            min = p

    else:
        print_non_blank.append(0)

        # Check 2
        for i in reserved(range(len(configurations))):
            if print_non_blank[i]:
                break
            if configurations[i].head_position < min:
                if configurations[i].state == configuration.state and configuration.head_position < configurations[i].head_position:
                    return REJECT
            elif configurations[i].head_position > max:
                if configurations[i].state == configuration.state and configuration.head_position > configurations[i].head_position:
                    return REJECT
            else:
                break

    # Check 3
    for i in range(len(configurations)):
        if configurations[i] == configuration:
            if sum(print_non_blank[i:]) > 0:
                return ACCEPT
            else:
                return REJECT

return REJECT

The decider $D$ maintains an area of the tape (represented by the closed interval $[$min$, $max$]$) such that there are only blank symbols beyond the interval. We call this area non-blank area, and call the area represented by $(-\infty,$min$)\,\cup\,($max$, +\infty)$ blank area.

In addition to count how many non-blank symbols $M$ prints (Check 1), the decider $D$ performs two additional check. Check 2 checks for the pattern where the head of $M$ wanders in the blank area without printing any non-blank symbol, then reach a position with the same state that is no closer to the non-blank area. Check 3 checks for the case where the configuration is the same as some previous one. We can assert that $M$ will loop forever in both cases and infer whether it will print more than $300$ non-blank symbols accordingly.

Now all the rest work is to show that $D$ is indeed a decider, i.e. will always halt. We prove this by contradiction. Assume $D$ does not halt for some $M$ and $w$, then $M$ does not halt on $w$ too. Also, $M$ must print finite ($\le 300$) many non-blank symbols otherwise $D$ will detect it and halt no later than the time $M$ prints the $301$th non-blank symbol. As a result, the non-blank area is always a subset of a fixed area represented by, say $[a, b]$, during the running of $D$. We call the area represented by $[a, b]$ universal non-blank area, and call the area represented by $(-\infty,a)\cup(b,+\infty)$ universal blank area. There are two cases.

  1. There are only finite many configurations where the head of $M$ is in the universal non-blank area. This means after some step, the head of $M$ will wander in the universal blank area forever (without printing any non-blank symbol, due to the definition of universal blank area), then there must be two configurations with the same state during the wandering. Also, the head of $M$ in the later configuration must be no closer to the non-blank area, otherwise the head will finally move into the non-blank area, which contradicts to the assumption that $M$ will wander in the universal blank area forever. As a result, this case is detected by Check 2 of $D$.

  2. There are infinite many configurations where the head of $M$ is in the universal non-blank area. In this case, there must be two same configurations, so this case is detected by Check 3 of $D$.

Hence $D$ will halt anyway.

$\endgroup$

Your Answer

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

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