6
You are committing a logical error. This question has nothing whatsoever to do with computability and machines. It is entirely about how to prove that something does not exist. Namely, to show the statement
$$\lnot \exists x . \phi(x)$$
we do as follows:
Assume that there is $x$ such that $\phi(x)$. We assume this even though perhaps we have no idea how to ...
5
This will be a partially inconclusive answer, unfortunately. Hopefully someone more knowledgeable can chime in and confirm the missing details. Let me summarize what I could find out so far.
Nondeterministic automata were introduced by Rabin and Scott in 1959. They also define two-way automata (which is a prelude to the LBAs introduced by Myhill the ...
3
An alphabet is a set of symbols, therefore if your you treat $\{a,b,c\}$ as a single symbol, it is a valid alphabet.
2
The machine $M$ is deterministic. This means that, if $M$ is in a certain configuration $c$, then there is a single fixed configuration $c'$ (determined by the rules of $M$) which the execution of one step will lead it to. If $M$ ever reaches the configuration $c$ again, then the configuration $c'$ will follow no matter what. Hence, if the computation of $M$ ...
2
There's is a significant difference between "arbitrarily long" and "infinite".
As a simple example, an integer can have an arbitrarily great magnitude; formally, for every integer, there exists a larger integer (its successor), which in turn has a successor, and so on. But all integers are finite; $\omega \notin \mathbb{N}$. (Or, if you prefer, $\infty \...
1
If $L_1,L_2$ are two languages over a common alphabet, then their concatenation is given by
$$ L_1 L_2 = \{ x_1 x_2 : x_1 \in L_1 \text{ and } x_2 \in L_2 \}. $$
If $L_1,L_2$ are r.e. then so is their concatenation. To see this, you can use the following algorithm. Given an input $x$, consider all possible partitions $x = x_1x_2$. For each partition, run a ...
1
If you have $g$ symbols (including a blank) and a tape of size $n$ then there are $g^n$ words of length $n$. This is really basic combinatorics: The reasoning is that you have $g$ options for the first symbol, $g$ options for the second symbol, i.e. $g^2$ options for the first two symbols. Then again $g$ options for the third symbol, giving you $g^3$ options ...
1
A language is recursively enumerable if there exists a Turing machine that:
halts and says "yes" whenever its input is in the language;
either halts and says "no" or just doesn't halt whenever its input is not in the language.
The undecidability of the halting problem means that there is no algorithm which, when given an RE language (or, rather, when given ...
1
Essentially, you're describing the PA degrees. The original definition was that something is of PA degree if it computes a complete consistent extension of Peano arithmetic (which by Godel must be non-computable), but there are many equivalent definitions. Generally the simplest to work with is:
A degree ${\bf a}$ is PA iff whenever $X$ is an infinite ...
1
The two sets are clearly different – there are Turing machines whose language is infinite but doesn't consist of everything. However, both languages belong to the same Turing degree, that is, each of them can be reduced to the other (computably).
Given an instance $M$ of ALLTM, construct a Turing machine $M'$ which on input $x$ runs $M$ on all inputs $y \...
1
What you describe is essentially Turing machines with advice, the advice for length $i$ being simply the description of $T_i$. It is a classic result that the two models are equivalent in the case of poly-time TMs and poly-sized circuits, that is, both produce the same class $\mathsf{P}/\mathrm{poly}$. If the description length of $T_i$ is allowed to be ...
1
You can simulate a state machine with set of states $S$ and registers $R_1,\ldots,R_m$ varying over a finite alphabet $\Sigma$ using a vanilla state machine whose set of states is $S \times \Sigma^m$. You "store" a value $x$ in register $R_i$ by transitioning to a state whose $(i+1)$'th element is $x$. You "read" a value from $R_i$ by taking into account in ...
Only top voted, non community-wiki answers of a minimum length are eligible
