New answers tagged

0 votes

Is there a Turing machine that packs a machine and its input into a single machine?

Irrespective of whatever notation is used by the OP, I will use the following notation: $T^k$ is the $k$-th Turing machine under an acceptable numbering of Turing machine, and $T^k(n)$ is the result ...
user avatar
  • 28.2k
1 vote

Showing that a property is semantic - Rice's theorem

Informally speaking, a property is semantic if it only depends on the final "outcome" of running $M$ on a given input rather than on the workings of $M$. In order to formalize this, with ...
user avatar
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 ...
user avatar
  • 141k
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 ...
user avatar
  • 1,055
0 votes

What would be an easy approach for this Turing machine description?

Instead of just checking "if a binary number is bigger than two", check whether the input is 0, 1, 2 or "big", where "big" means greater than 2. Assume the most ...
user avatar
  • 34.1k
0 votes

Help with two-tape Turing Machine for $L = \{ a^{n^2} | n \ge 0 \}$ - clarification needed

I'll let the mods decide if it's a duplicate or not, but I do agree that the explanations could warrant a bit more explicit explaining. You have two tapes, one of them is the one with the input, and ...
user avatar
  • 304
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 ...
user avatar
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. ...
user avatar
  • 34.1k
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 ...
user avatar
  • 34.1k
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 ...
user avatar
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$. ...
user avatar
  • 141k
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 $...
user avatar
  • 23.4k
0 votes

How is the computational power of a human brain comparing to a turing machine?

In theory, a Turing machine has enough power to simulate all the molecules in a brain, so there is no doubt that it is as capable. We can also argue that in some decades, AI will be able to reach ...
user avatar
  • 3,911
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 ...
user avatar
  • 111

Top 50 recent answers are included