30
The correct version of the claim states that every computable language is accepted by infinitely many Turing machines.
Indeed, if $L$ is computable, then there is a Turing machine $T$ that accepts it. Let $T_n$ be $T$ together with $n$ unreachable states. Then $T_n$ also accepts $L$, and the machines $T_n$ are all different from one another.
19
Intuitively?
Do you know programming? Can you think of a way of making infinitely many versions of the same program?
Say, adding a function foo that you never call creates a different program, but it still does the same thing.
6
Note that the quoted sentence should be "R. This is the empty set, since every $\text{L(M)}$ has an infinite number of TMs that accept it."
The other answers are correct, and there are other ways to prove that every language that is accepted by some TM, is actually accepted by $\aleph_0$ distinct TMs. However, following the last sentence in the ...
5
Fix a value of $n$. For $b \in \{0,1\}^n$, consider the following algorithm $A_b$:
If $x \leq n$ then output $b_x$, otherwise output $0$.
Clearly one of the $2^n$ algorithms of the form $A_b$ computes your function $h$, hence $h$ is computable.
5
Just put a for loop in there. It goes around n times before doing the calculation. There is no limit to the size of n.
4
This shouldn't come as a surprise, but you should definitely be familiar with algorithms and datastructures as well as complexity theory.
Two fundamental text books are downloadable for free, and you can probably find the answer to your question there:
Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michal ...
3
The subtle idea of computability of finite sets is that we don't necessarily need to know which TM machine actually decides that set or how it is internally. We just need to know that some TM decides that finite set.
Given $n$, there are (infinite) Turing Machines that decides every subset of $\{0,1,\dots{},n\}$.
You don't know which one is the set for which ...
3
A system is Turing-complete if it is at least as powerful as Turing machines.
A system is Turing-equivalent if it is exactly as powerful as Turing machines.
An example of a Turing-complete system which is not Turing equivalent is Turing machines with oracle access to an oracle for the halting problem.
One can come up with one additional definition to ...
2
The answer to the first question is quite simple. Suppose that $f$ is a mapping reduction from $A$ to $\overline{A}$. Then $f$ itself is also a mapping reduction from $\overline{A}$ to $A$. I'll let you verify that.
Next, let us show that if $A,\overline{A}$ are both RE, then $A$ is in R. How to show that depends on your definition of RE.
RE is the set of ...
2
It follows immediately from the definition of a mapping reduction that a reduction $f$ from $A$ to $B$ is also a reduction from $\overline{A}$ to $\overline{B}$. Indeed, if $f$ is a reduction from $A$ to $B$, then, in particular, $x\in A$ iff $f(x)\in B$, which is equivalent to $x\notin A$ iff $f(x)\notin B$, which is equivalent to $x\in \overline{A}$ iff $f(...
2
The quoted claim is very unfortunate. First because it is written in a clumsy way which makes it wrong as Yuval wrote. Two because it is a huge hammer to smash a tiny nut - all you need is to show that any TM can be modified slightly (usually by making it a tiny bit less efficient) while recognising the same language.
2
As mentioned in the above comment, the format of your reduction is not correct, so you have to take care of that first, and think about it again. Also, the hint I gave in the question that you linked should be enough. Anyway, here is another hint.
Hint: consider the identity reduction that maps every word $x$ to itself, and try to understand why it does not ...
2
The author is here referring to the Halting problem, and possibly also Rice's theorem (without putting words into their mouths).
It says indeed that it's not possible to decide in advance whether a Turing machine will halt on any given input or not, thus it makes it impossible to decide in advance what the actual output of the machine will be.
This is the ...
1
Several authors have considered this question. If you look at some recent work, it will cite older work. The most recent I am aware of is Pieter Hofstra's and Robin Cockett's work on Turing categories, see Definition 3.1 in their Introduction to Turing categories.
1
Assume that all languages are over the alphabet $\Sigma$. What you have here is a bit of ambiguity in the meaning of $\emptyset$ (recall that the emptyset is defined w.r.t a universal set, and here $\emptyset$ is used w.r.t different universal sets). Indeed, $S = \{ \emptyset\}$ refers the set of languages containing only the empty language, that is, in ...
1
I'll assume that $R$ is the set of recursive languages and that in the definition of $NPA$ we are talking about Nondeterministic Polynomial Time.
You are just proving that, for $L \in R$, $L \subseteq Disagree(M_1, M_2)=\Sigma{}^*$ which says nothing about $NPA = R$.
To accept a language $L$, there must be some machine $M$ such that for each string $x \in ...
1
You could start from the fact that the language $HP$ of the Halting problem is r.e. If its complement $\overline{HP}$ were r.e. too then that would mean that $HP$ is recursive (in $R$) which is impossible.
Next, if there were at least one $k$ such that $L(M)^{\ge k} = \overline{HP}^{\ge k}$ then we could use this Turing machine $M$ to prove $\overline{HP}$ ...
1
The intuition is that finite languages are very simple in the sense that throwing a finite number of words from a language does not affect membership in $\text{R}$ or in $\overline{\text{RE}}$, etc. Therefore, since $L^{\geq k}$ is the result of throwing a finite number of words from $L$, we get that:
$L(M)^{\geq k} \in \text{RE}$, and
$\overline{HP}^{\geq ...
1
What confuses you is that the words in the languages are encodings of machines that simulate runs of other machines, but at the end of the day, these are just words. Specifically,
given input $x = \langle M, x\rangle$ for the reduction, the reduction itself does not simulate the run of $M$ on $x$, the reduction only outputs $f(x) = \langle M'\rangle$ which ...
1
When we implement a space we do not actually implement the space itself, but rather a representation of it. That is, an implementation of $X$ consists of a datatype $T$ and a partial surjection $\delta : T \to X$, as in Type Two Effectivity. When $\delta(p) = x$ we say that the datatype value $p \in T$ represents or realizes the point $x \in X$. Cruicially, ...
1
Yes, "that terminates" is the halting problem, not really in disguise but also not pointed out as problematic.
1
Let $\Sigma$ be the alphabet on which $A_{TM}$ is defined over, and assume w.l.o.g that:
$A_{TM}\cup \overline{A_{TM}} = \Sigma^*$, and
$0, 1 \notin\Sigma.$
The set $J$ can be written as:
$$
J = \{0\}\cdot A_{TM} \ \cup \{1\}\cdot \overline{A_{TM}}
$$
where $J$ is defined over the alphabet $\Sigma \cup \{ 0, 1\}$.
Now, using De morgan's law, it holds that:...
1
The language $L$ is not decidable, this is an immediate consequence of Rice's theorem (you can instead try and prove that $L$ is not decidable directly using reductions). To begin with, there are two machines $M_1$ and $M_2$ such that $L(M_1)\in coRE$ and $L(M_2)\notin coRE$. For example, $M_1$ can be a machine that accepts all inputs, and $M_2$ can be a ...
1
If you know Dynamic Programming, I would say you won't face a lot of difficulties studying it. You need to have basic knowledge of design and analysis of algorithms and dynamic programming at least. You can start with Tree-Width and Dynamic Programming. That would be a great place to start studying this topics. Then you will find one thing called 'Nice Tree ...
1
Of course you can unwind self modifying code to some sort of semantic equivalent version. However, self modifying code where timing and external state or internal cache behavior is part of what influences the output CANNOT be represented except by anything beyond perhaps a good high level description language with a compiler or translator that can take that ...
Only top voted, non community-wiki answers of a minimum length are eligible
