The Gateway to Computer Science Excellence
0 votes

Informally describe multitape Turing machines that enumerate the following sets of integers, in the sense that started with blank tapes, it prints on one of its tapes $10^{i_{1}}10^{i_{2}}1\cdot\cdot\cdot$ to represent the set $\left\{i_{1},i_{2},\cdot\cdot\cdot\right\}$.

  1. The set of all perfect squares $\left\{1,4,9,\cdot\cdot\cdot\right\}$. 
  2. The set of all primes $\left\{2,3,5,7,11,\cdot\cdot\cdot\right\}.$
  3. The set of all $i$ such that $M_{i}$ accepts $w_{i}$. Hint: It is not possible to generate all these $i's$ in numerical order. The reason is that this language, which is $\overline{L_{d}}$, is $RE$ but not recursive. In fact a definition of the $RE$-  but-not-recursive languages is that they can be enumerated, but not in numerical order. The "trick" to enumerating them at all is that we have to simulate all $M_{i}'s$ on $w_{i}$, but we cannot allow any $M_{i}$ to run forever, since it would preclude trying any other $M_{j}$ for $j\neq i$ as soon as we encountered some $M_{i}$ that does not halt on $w_{i}$. Thus we need to operate in rounds, where in the $k^{th}$ round we try only a limited set of $M_{i}'s$ and we do so for only a limited number of steps. Thus each round can be completed in finite time. As long as for each $TM \ M_{i}$ and for each number of steps $s$ there is some round such that $M_{i}$ will be simulated for at least $s$ steps, then we shall eventually discover each $M_{i}$ that accepts $w_{i}$ and enumerate $i$. 
in Theory of Computation by Veteran (58.7k points) | 4 views

Please log in or register to answer this question.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,274 answers
104,798 users