4
votes
Accepted
Turing Machines time complexity with regard to the NP and P problem
What are the 'advantages' of a deterministic TM over the non-deterministic one?
The advantage of the deterministic TM is that deterministic Turing Machines represent the type of computation we are ...
- 1,035
3
votes
Accepted
Worrying about details: high-level arguments about polynomial-time computability
The way you convince yourself of those claims is that you figure out how to write out an explicit proof of them. This same issue occurs with every mathematical proof. Every mathematical proof has ...
D.W.♦
- 141k
3
votes
Accepted
Limited tapes-version TM for pair sum
Summary: There is no need to sort the given numbers since whether there are two numbers in $A$ such that their sum is $\alpha$ depends on the set of numbers in $A$.
Since the choices for the set of ...
- 34k
3
votes
Accepted
Can a Turing machine quickly move to any position of a large string?
It depends.
1: If there are at least $\lceil \lg |s| \rceil$ unused cells after the end of $s$ and the head starts within $s$, then the answer is yes.
Here is how. Start from the beginning of $s$. ...
D.W.♦
- 141k
2
votes
Accepted
Turing Machine writes "a" for every input w is undecidable
Your suspicion is well-founded. The point 4 is invalid.
Imagine the exact moment N "writes 'a' on the tape and reject" in the point 4. That means at that moment, it is known that M loops. ...
- 34k
1
vote
Accepted
Are deterministic Turing machines as powerful as probabilistic Turing machines?
This is a famous open problem in computer science theory. In particular, it comes down to whether BPP = P. It is widely conjectured and suspected that BPP = P, or in other words that randomness does ...
D.W.♦
- 141k
1
vote
Accepted
Determining whether the problem of given a turing machine figuring out whether the language it accepts is the set of prime length inputs is R.E
I think your reduction is correct. Indeed, the reduction is clearly computable and furthermore if the original Turing machine $M$ halts on (the fixed) input $w$, then the set of words accepted by the ...
- 261
1
vote
If A is Turing-reducible to B and B is Turing recognizable then A is Turing recognizable
The statement is false.
Consider the language $H$ of the halting problem and let $H'$ be its complement.
$H'$ is Turing reducible to $H$ and $H$ is recognizable, however $H'$ is not recognizable (if $...
- 23.3k
1
vote
Decidability of intersection of regular and decidable languages
I don't quite understand what you mean by if (A) is decidable then it is a language in R, if you mean that A is regular and B is regular then the intersection of two regular languages is still regular....
- 456
1
vote
How is the computational power of a human brain comparing to a turing machine?
Here is a question on Turing completeness of neural networks.
In my answer, I also discuss the human brain a bit, and I reference also this question here.
I think allowing for some type of infinite ...
- 111
1
vote
Is there a TM that halts on all inputs but that property is not provable?
The halting of one TM can be encoded by constructing another TM and asking whether it halts. That is, given TM $T_1$ and input $I_0$, we can construct a TM $T_2$ with inputs indexed by the natural ...
- 710
Only top scored, non community-wiki answers of a minimum length are eligible