2
The problem is not clear enough. Turing Machines can or cannot solve problems if those problems are languages, that means, sets of strings over a finite alphabet. You cannot represent all reals in this way, so it is not even a problem that a TM could even attempt to solve. In the same fashion that world hunger is not a problem in the precise sense that a ...
2
There are multiple notions of "reduction." You've correctly described a many-one reduction of $HALT$ to $A_{TM}$. The reduction you've linked to (more specific link here) is instead a truth-table reduction. These are more general objects (so your result is stronger). Each is in turn subsumed by the much broader notion of Turing reduction.
While many-one ...
2
There are a few keywords in the excerpt from the said text book - non-trivial, problem, property.
Now what is a problem, assuming we are not dealing with combinatorial optimization problems,i.e. we are dealing with only questions which have an YES or NO answer to them.
When you ask a YES or NO question to an input string if the answer is YES you place it in ...
2
Sure. Any Turing machine can be represented as a bit string (print out the description of the Turing machine). Any bit string can be encoded as a natural number (prepend a 1 bit, and view it as a binary representation of a number).
2
Suppose that $f$ is injective. Consider the following nondeterministic machine for $L$: on input $w$, the machine guesses $z$ of size between $|w|^{1/k}$ and $|w|^k$, and verifies that $f(z) = w$. Since $f$ is injective, if $w \in L$ then there is exactly one witness $z$, and so $L \in \mathsf{UP}$.
Since $L$ is always in $\mathsf{NP}$ (using the very same ...
1
Your machine uses $n + k = O(n)$ space. As such, it can be simulated by a linear bounded automaton. The latter is known to be weaker than a general Turing machine. For example, it cannot solve the halting problem for machines using $n^2$ space, a problem that Turing machines are able to solve.
1
To follow the strategy you outline, we need to be confident a priori that we have an upper bound on $BB(n)$. More snappily, if $f$ is any function with $f(n)\ge BB(n)$, then from $f$ we can compute the halting problem: given an $n$-state machine, run it for $f(n)$-many steps.
Since the halting problem isn't computable, this means that no such $f$ is ...
1
It seems you're working towards the notion of Turing reducibility. For example, adding a nontriviality assumption you're roughly asking here:
Is there a set which is not computable but also does not compute the halting problem?
This is an excellent question, and the answer is far from obvious - but ultimately yes in a very strong sense (although a ...
1
Given the length of the input $n$, you can come up with a bound $N(n)$ on the number of configurations that the Turing machine can have. If the machine hasn't stopped on an input within $N(n)$ time steps, then it will never stop (why?), and you can use this to complete the proof. Details left to you.
1
Both definitions are the same. They just use a different wording. The difference between "decide" and "accept" is commonplace in computability theory, but in complexity theory different terminology is typically used, since we usually deal with machines that always halt.
The class $\mathsf{P}$ consists of all languages $L$ for which there exists a Turing ...
1
The halting problem, $\mathsf{HALT}$ reduces to $\overline{L_2}$.
Given a TM $T$ and input $w$, create a new TM $N$ that on any input of length $n$, simulates $T$ on input $w$ for $n$ steps and then stops except that if $T$ ever halts before $n$ steps, $N$ will move its head to the right forever.
There is a gap in the above reduction. When $N$ simulates $T$...
1
Sure, the idea is basically that you're going to turn the first 0 into blank, and then go search for the last 1 and turn it in into blank, then go back to the beginning and proceed recursively in the same fashion.
Here's an implementation on the online turing machine simulator
1
Yes, listing out all the transitions would be tedious so I'll just give you the high level algorithm (the idea is to iteratively match the first 0 with the last 1, while deleting both of them). Starting from the first symbol on the tape do the following:
If the current symbol is $\varepsilon$: accept
If the current symbol is $1$: reject
Delete the current ...
1
Suppose that there is a Turing machine $T$ that decides $E_{TM}$.
Given a turning machine $M$ and an input $w$ you can construct a new Turing machine $M^*$ that decides whether $(M,w) \in H_{halt}$. $M^*$ operates as follows:
It first constructs a new Turing machine $M'$ that ignores its input, simulates $M$ on input $w$ and, once the simulation is ...
1
Yes. Actually, it is even true that for every language $L_1$ there is a language $L_2 \supseteq L_1$ such that $L_2$ is regular.
Proof: Pick $L_2 = \Sigma^*. \square$
1
Yes, a state can go to itself when seeing any symbol. (As Steven's answer says, the analogous question for head movement - whether the head of the Turing machine has to move at each stage, or whether it can stay put at a given moment - varies from definition to definition, but I've never seen a definition which prohibits a state from looping to itself.)
...
1
You cannot construct an explicit algorithm/TM which will decide the language $L_k$. Regarding your attempt at the proof: you are right that there is no guarantee that the configuration will repeat because these machines are not given to be space bounded.
The TM $M_k$ to decide $L_k$ will have all the tuples (which are finite in number) which are accepted ...
1
No, they are not the same.
There are different equivalent representations for any problem (e.g. Turing machines, neural networks, differential equations, ...). But changing from one representation to another does not change whether the problem is fundamentally solvable - otherwise they would not constitute equivalent representations.
Zeno machines can be ...
1
Suppose we allow an algorithm to return "Yes, it halts", "No, it doesn't halt", or "I don't know". Then the proof no longer applies; and in fact this modified version of the halting problem is decidable. For instance, a very simple algorithm could always output "I don't know", and it'd never be wrong. Unfortunately, that very simple algorithm probably isn'...
1
It doesn't matter if and when some newly defined machine $M$ outputs an extra value - the original machine $H$ of the halting problem still leads to a contradiction.
The proof of the halting problem relies on showing that if we assume there is an oracle machine $Q$ solving the halting problem that we can construct a machine $H$ that uses $Q$ such that a ...
Only top voted, non community-wiki answers of a minimum length are eligible
