# Tag Info

1 vote

### A question about the number of states of a Turing machine using the alphabet $\{ 0, 1, \square, \rhd \}$

In the suggested sketch, the machine $\widetilde{M}$, upon simulating a step of $M$, needs to remember, in its state-space, the following information: The current state of $M$ -- there are $|Q|$ ...
• 3,793
Accepted

### Decidability of Turing Machine

When a machine performs at most 10 steps, then it can reach at most 10 tape-cells. In particular, the tape's content that lies right to the 10'th tape cell does not affect that machine's computation. ...
• 3,793
Accepted

### Computation theory: decidability and Turing-recognition

1- In the deterministic setting, quickly acceptance and acceptance coincide. Hence, a deterministic machine $M$ quickly recognizes a language $L$ iff it recognizes $L$. As there are languages that can ...
• 3,793
Accepted

• 3,793
Accepted

### Classifying a language of TM encodings

As @Knogger pointed out, the machine $M'$ in the definition of $L$ contains at least 3-states (the initial state $q'_0$, which is distinct from the accepting and rejecting states), which makes the ...
• 3,793

### Is the unsolvability of the N-Body Problem equivalent to the Halting Problem

Almost certainly it is possible to build (conceptually) a Turing machine using gravitational components. A google search of "square orbits" shows that the flow of particles in a ...
Accepted

### Proving Rice's theorem extension

You need to run the machines $M$ and $M_A$ in parallel, as we cannot simply run the machines consecutively -- this is a basic trick, where we cannot simply wait for one machine to halt as it may not, ...
• 3,793
1 vote

### Why can one define a Turing Machine by its "description"?

Just as we can compile (high-level) programming languages to machine code, we can also compile programming languages to Turing machines. That was generally accepted as feasible, just very tedious and ...
• 590
Accepted

### Why can one define a Turing Machine by its "description"?

Formally, a Turing machine is defined by a 7-tuple, as specified by the mathematical definition. See https://en.wikipedia.org/wiki/Turing_machine#Formal_definition. Informally, if I give an English ...
• 163k
1 vote

### How to prove a problem is EXP hard

This is an immediate consequence of the fact that $\text{APSPACE} = \text{EXPTIME}$ (see, for example, here). Specifically, consider a language in $L \in \text{EXPTIME}$, and let $T$ be an alternating ...
• 3,793
### Prove that $n$ is a time-constructible function
You essentially need to describe a TM $T$ that given input $x$ computes the binary representation of $|x|$. Note that a full proof does not require you to define every component of the machine ...