New answers tagged turing-machines
0
votes
Accepted
need to prove that $DSPACE(O(2^n)) \neq EXP$
I agree that such an $L$ exists by THT and that $L_{pad}\in \text{DTIME}(2^n),$ but from there I'm not really grasping your argument. Where is $L_{pad}\in \text{DSPACE}(O(2^n))$ (or anything about ...
1
vote
Definition of semi-infinite tape Turing machine
There are several ways how the definition can go. Besides having a special symbol marking the boundary of the tape as in GKxx’s answer, some possibilities are:
Define one step of the computation of ...
- 2,222
1
vote
Accepted
Definition of semi-infinite tape Turing machine
I think the definition must be attached with a definition of the language that it accepts. I come up with a definition similar to that of LBA (linear bounded automata):
A semi-infinite tape Turing ...
- 126
2
votes
Accepted
$SET-COVER\leq_pIP$
Given $(U, S_1, …, S_m, k)$ an input of Set-Cover, with $U = \{1, …, n\}$, consider an $n\times m$ matrix with $0$-$1$ coefficients, such that $A_{ij}$ represents $i\in S_j$.
Consider $b$ an $n$-...
- 16.9k
1
vote
Must an algorithm terminate to be in NPTIME?
A proper definition of $\mathsf{NP}$ (or $\mathsf{NPTIME}$, as you seem to call it) should have been given in your course. You need to check the definition to see whether it requires all branches of ...
- 2,222
3
votes
Why does nondeterministically estimating a number have exponential time complexity?
First, Sipser was talking about a deterministic algorithm, not a non-deterministic one.
Second, the machine you describe does not solve the problem $\texttt{PRIME}$, because it returns true when it ...
- 16.9k
2
votes
Must an algorithm terminate to be in NPTIME?
Remember, NP is capturing the idea that you can check a solution in polynomial time. So in this case, if you are given a number, you can easily verify if it is a nontrivial factor of your input or not....
- 308
3
votes
Can't we model a probabilistic turing machine using deterministic turing machine?
A deterministic Turing Machine is a piece of mathematics. It has a mathematical definition. Different textbooks and different articles use slightly different definitions, but they are all very similar,...
- 5,941
3
votes
Accepted
Infinitely-taped (& "headed"!) Turing Machine: "Stronger" Than Standard
Such a machine can indeed compute every function of type $f : {0,1}* \to \{0,1\}^*$. The gist of the proof is that the transition function has domain $S \times \Sigma^\omega$, where $S$ is the (finite)...
- 3,293
0
votes
Writing a Turing Machine that convers a number from binary to decimal
A mostly straightforward 3-state solution (on a 2-tape Turing machine, so if you want a single-tape TM, you still have to do something): https://turingmachinesimulator.com/shared/kshuxghzgd
- 2,222
-1
votes
Writing a Turing Machine that convers a number from binary to decimal
Wrote crappy one in simulated touring machine website : https://morphett.info/turing/turing.html?3a4f4d04f5416ee756a6983d87537e46
- 1
Top 50 recent answers are included