39
Sure. Electricity is unrelated to the model of computation.
The only thing you can't actually build is the infinite tape, for obvious reasons. In this sense, anything that can be built is essentially equivalent to a deterministic finite automaton.
Here's a Turing Machine made of wood:
https://www.youtube.com/watch?v=vo8izCKHiF0&ab_channel=RichardRidel
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.
24
Sure. Not only is it possible, the first design for a Turing-complete computer was purely mechanical. This was Charles Babbage's Analytical Engine. Babbage published its design in 1837, long before electricity was considered a practical source of energy, and even longer before electronics was even imagined.
The Analytical Engine was inspired by looms. ...
answered Dec 30 '20 at 12:13
Gilles 'SO- stop being evil'
39.8k7 gold badges105 silver badges170 bronze badges
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.
7
The first definition you are referring to is probably the one that defines $\mathsf{NP}$ as the set of problems $\Pi$ for which there exist a non-deterministic poly-time Turing machine that decides $\Pi$.
Since any problem $\Pi \in \mathsf{P}$ can be decided by a deterministic poly-time Turing machine $T$, and $T$ itself is also a non-deterministic Turing ...
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
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.
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 ...
3
Let us say that $H$ is a partial Halting oracle if it takes as input a pair $(M,x)$ where $M$ is the description of a Turing machine and an input $x$, and:
If $H$ terminates and outputs "yes" then $M(x)$ halts.
If $H$ terminates and outputs "no" then $M(x)$ does not halt.
In particular, $H$ is allowed to run forever and not give an ...
3
The problem of deciding whether, given a Turing machine $T$ and a word $w$, $T(w)$ halts is undecidable.
If a Turing machine $T$ is fixed, the problem of deciding whether, given a word $w$, $T(w)$ halts might or might not be decidable (depending on the choice of $T$).
As an example in which this problem is decidable consider the trivial Turing machine $T$ ...
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
See: YouTube
Matt Parker has made some small scale logic gates out of dominoes. Highly impractical, but theoretically, with enough time and space, one could build a functional computer that way. Apparently
2
I will give a general algorithm going through intermediate steps that can be implemented in polynomial time, each. Yet, I will not dive into the details of how to implement each step. The solution I'm suggesting may not be optimal, yet it is easy to understand. Essentially, we're going to rely on basic properties of Pushdown automata (PDAs, for short).
Let $\...
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
If $M$ does not have the option to not move its head at all, as stated in a comment to the question, then the problem is trivially decidable by the Turing machine that immediately halts and accepts.
If $M$ might not move its head while computing $T(w)$ and the problem is to decide whether it actually does so, then the problem must be undecidable as otherwise ...
2
A configuration of a TM is usually defined as $uq\sigma v$, where $u\sigma v$ is the tape's content up to a cell from which there are only blanks, $q$ is the current state, and the head of the machine points at the letter $\sigma$. So the place of the state $q$ in the configuration $uq\sigma v$ is there simply to indicate at which letter the head points. ...
2
As you suggested, think how to reduce from the halting problem $Halt_{TM} = \{ \langle M, w\rangle: \text{$M$ halts on $w$} \}$. On input $\langle M, w\rangle$, the reduction should output a pair of TMs $\langle K_1, K_2\rangle$; such that $M$ halts on $w$ iff $L(K_1) = L(K_2)$.
This is somehow a basic reduction that can be done by standard tricks, so it ...
2
The application of the theorem is not correct. Note that $\mathcal{L}$ is a set of acceptable languages, and consider your first point. If you take an acceptable language $L$ that contains a string of length 2014, then it is not necessarily that every superset of $L$ is acceptable.
Regarding the last point, the answer is yes. Given an encoding $\langle L\...
2
In general, whenever you try to design a machine accepting a language with this kind of "finite conditions", the easiest solution is to hard-code those conditions directly into the states of your machine.
Here, you would have 24 "counting" states, labelled by $(g, t)$ for $0 \leq g \leq 5$ and $0 \leq t \leq 3$. Whenever you read some $G$ ...
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
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
Let's say that $f:\Sigma^* \to \Sigma^*$ is a reduction from $A\subseteq \Sigma^*$ to $B\subseteq \Sigma^*$. A flowchart graph of $f$ looks like:
Indeed, $f$ maps all words in $A$ to $B$, and all words in $\overline{A}$ to $\overline{B}$.
The closest flowchart to the image that you attached corresponds to the reduction theorem, to be explined below. (You ...
1
The arrow is going from $A$ to $B$. It means you are solving problem $A$ using problem $B$. So, it is a reduction from $A$ to $B$
1
For $L_1$, consider a computation $T(w)$ of a Turing machine $T$ that never moves its head to the left with input $w$. Let $\Gamma$ be the tape alphabet (including the blank symbol) and $Q$ be the set of states of $T$.
Notice that, at any given step during the computation, the future behavior of $T(w)$ is completely determined by:
The current state.
The ...
1
A Turing machine $T$ decides the halting problem if on input $\langle M,w \rangle$:
If $M$ halts on $w$, then $T$ halts and outputs "Yes".
If $M$ does not halt on $w$, then $T$ halts and outputs "No".
In order to show that $L$ is not recognizable, you assume that $L$ is recognizable, and use that to construct a Turing machine $T$ which ...
1
I am assuming that $A$ is a non-trivial problem. If $A$ is trivial, then the claims cannot be correct in their current form (make sure you understand why).
Consider an NP-complete problem $B$, and consider some non-trivial problem $A \in \text{P}$. Clearly, $A\leq_p B$. If we assume that claim 2 is correct, then as $A\leq_p B$, we get that $A$ is $\text{NP}$...
1
Edit: the answer assumes that the tape of a TM is left bounded, that is, the tape has a leftmost cell.
Given $\langle M, w\rangle$, $M$ does not move its head while running on the input $w$ when its in never the case that the head of $M$ is at the leftmost and the next transition suggests that $M$ moves its head to the left. Now can we decide whether this ...
1
is EVEN undecidable? How can you prove its undecidability?
It depends entirely on the enumeration that you use. E.g. one could make an enumeration that maps all Turing machines that halt with 1000 steps to an even index and all others to odd indices. Then EVEN is still an infinite set but decidable.
However a simple way to prove EVEN undecidable (assuming ...
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:...
Only top voted, non community-wiki answers of a minimum length are eligible
