Trying to describe this Turing Machine

168 Views Asked by At

Let's say I have the following turing machine:

$F_n$ = {M | M is a TM and |L(M) ≤ n}

In english, for some given natural number n, $F_n$ is the language of all turing machines that accept no more than $n$ strings. We want to prove that for all values of $n$, that $F_n$ is co-RE.

I need to describe a turing machine that is a co-recognizer for $F_S$, which means that it must reject all M if there exist more than $n$ strings that $M$ accepts.

2

There are 2 best solutions below

2
On BEST ANSWER

Let $E_n = \{M : M \text{ is a TM and } |L(M)| > n\}$.

Note that $E_n$ is the complement of $F_n$. To show that $F_n$ is co-r.e., one needs to show that $E_n$ is r.e.

As usual Turing machines are coded by natural numbers and Turing machines take input natural numbers. (All other alphabets can be coded as natural numbers.)

So a Turing machine $U$ that accepts $E_n$ is as follows: On input $e$ (which is the code of machine $T_e$), simulate $T_e$ first on input $0$ for $0$-steps, then simulate $T_e$ input $0$ and $1$ both for $1$ step, then input on $0$, $1$, $2$ all for $2$ steps, etc. Halt at step $s$ only if ever you find $n + 1$ numbers less than $s$ such that $T_e$ halts within $s$ steps.

The machine described above will accept $E_n$. So $E_n$ is r.e. Hence, $F_n$ is co-r.e.


I have never heard of a co-recognizer; however, from the definition you provided above, it would essentially be the same machine above except where I said halt, you would reject.

0
On

Run all programs on all inputs and keep track of how many inputs each program has halted on so far. Whenever a program has halted on $n+1$ inputs, output it. This enumerates the complement of $F_n$ so $F_n$ is in co-RE.