New answers tagged

0

I describe an NFA construction method for a non-deterministic Turing machine. Let's fix an input and fix a run of the Turing machine. Let $M$ be the maximum tape cell index visited by the run. For $1 \le i \le M$, let $1 \le k_i \le K$ be the number of times tape cell $i$ is visited, where $K$ is the maximum visit count. The head movement of the Turing ...


1

They are still turing complete. Here is some intuition for why: You can manually "clear", say, the first $100$ positions by replacing them with a blank. Then, we can "split" the tape into two parts by writing a special character $\#$, for which the first half are all of the tape contents before the first occurrence of $\#$ and the rest of ...


1

You use dovetailing to simulate all possible execution paths of the NTM.


0

As stated by Ordoshsen, if $A$ is a regular language, then: $$A \in \mathsf{SPACE}(1)\subset \mathsf{SPACE}(\log n)\subset\mathsf{SPACE}(n)\subset \mathsf{SPACE}(n^2)\subset \mathsf{SPACE}(2^n)$$ so all answers a, b, c and d are true. To prove that $A \in \mathsf{SPACE}(1)$, consider a DFA $D = (Q, \delta, q_0, F)$ such that $A = L(D)$. Consider a two-tapes ...


1

The input of $K$ is $x$, and $K$ will only simulate $M$ during at most $|x|$ steps. Therefore, there is no situation where the simulation of $K$ does not stop. If $M$ does not accept $w$, then for any word $x$ of length $n$, executing $M$ during $n$ steps will never reach an accepting state. And so, after $n$ steps of simulation, the TM $K$ will accept the ...


4

Your function is well-defined, that is, total. The value of $f(n)$ is the maximum of the finite set $\{g_1(n), \ldots, g_{w(n)}(n)\}$. The maximum of a finite set of numbers always exists. Your function is computable iff $w$ is bounded. Suppose first that $w$ is not bounded, and assume for the sake of contradiction that $f$ were computable. Then $h(n) = f(n) ...


1

Typically, no, this is not possible. It depends on how the infinite set is represented. (I'm assuming it's a set of integers.) The usual way to represent a possibly-infinite set $S$ is as a Turing machine $M$: $M$ enumerates all the elements of $S$. For this representation, it is uncomputable to determine the maximum element of $S$. That is, on input $\...


0

The space complexity is defined for TMs. You have to come up with an algorithm (Turing machine) that uses as little space as possible and calculate its space complexity.


1

The answer depends on the coding of $n$. The set $\{(M,x,1^n) | \text{ TM } M \text{ accepts }x \text{ within } n \text{ tape space } \}$ is $PSPACE$-complete. But the set $\{(M,x,n) | \text{ TM } M \text{ accepts }x \text{ within } n \text{ tape space } \}$ where $n$ is binary coded is $EXPSPACE$-complete.


0

Based on the review that I received, I fixed the second part of the proof. I would like to know if it's correct now, I would appreciate your input on this. Let us construct an NP machine M for $\overline{L}$ that gets the input x. Since we know L is accepted by a nice machine, let N be the nice machine for L. 2.1. The machine M guesses one particular path ...


0

Regarding your answer, here are some corrections. For part (1), your argument is partially correct but incorrectly stated. For part (2), your argument is not correct. Your biggest mistake is in the way you describe nondeterministic Turing machines. Remember that a nondeterministic Turing machine does not magically have access to all possible paths at once -- ...


0

Can I prove the first direction in the following way? Let us construct an NP machine for L that gets the input x. 1.1 The machine guesses all the possible paths for the given input. 1.2 The machine checks if any non-quit path exists. 1.3 The machine checks whether the value of all the 'Accepts' and 'Rejects' paths are equal. If both 1.2 and 1.3 are true, ...


1

First hint: construct a TM that converts the input into a unique natural number Second hint: encode the language directly in the turing machine, by specifying which natural number is considered a part of the language and which one isn't.


1

If H(x,x) goes into an infinite loop, then that fact already proves that H does not solve the halting problem. If H solves the halting problem, then it never goes into an infinite loop. If we are trying to figure out whether it's possible to solve the halting problem, we can ignore all the functions that sometimes enter infinite loops. They obviously don't ...


5

No. The difference between a Turing machine and a finite automaton is in the amount of available work space: Finite automata are equivalent to Turing machines with finite tapes. Indeed, any finite automaton can be encoded as a Turing machine that requires no additional work tape. Conversely, a Turing machine whose work tape has finitely many cells has a ...


2

It depends what you mean by "pure". Without knowing what you mean by it, it seems hard to say. See https://en.wikipedia.org/wiki/Pure_function for one possible meaning. That notion relates to the input-output behavior of the system, and Turing machines and finite-state automata can be viewed as systems that meet those requirements. It is true ...


Top 50 recent answers are included