New answers tagged

0

I want to add two points, not mentioned in earlier examples, to supplement them. The Church-Turing thesis was made clear when Turing invented the Turing machine: It's valuable to have one or more concepts that means something roughly like "possible to calculate algorithmically, in principle". If a problem is not of this kind, then it's not the sort of ...


2

Maybe the Turing Machine Linear Speed Up Theorem will answer your doubt (https://en.wikipedia.org/wiki/Linear_speedup_theorem) Counter-intuitively or maybe intuitively, this states that given a Turing Machine which does something in say $n$ steps there are Turing Machines which can solve the same problem in $n/k$ steps for any constant $k$ independent of $n$...


2

As Wikipedia says, there are two conditions for strongly polynomial time algorithms: the number of operations in the arithmetic model of computation is bounded by a polynomial in the number of integers in the input instance; and the space used by the algorithm is bounded by a polynomial in the size of the input. I will simply call these two ...


3

The idea is quite simple. We are going to simulate running $M_f$ (the machine for $f$) on $g(x)$. Let $m = |g(x)|$, and note that $\log m = O(\log n)$. In order to do that, we keep track of the location of the input tape head of $M_f$ (this takes $O(\log m)$ space), as well as the contents of the work tapes (which also takes $O(\log m)$ space). Whenever $M_f$...


1

First we assume for the $S_3$ is decidable and let TM $R$ be the decider for $S_3$. With $R$, we can test whether $M$ writes symbol $``3"$ on the third cell of its tape at some point. If $R$ indicates that $M$ doesn't write $``3"$ on the third cell, reject because $\big \langle M,3 \big \rangle \notin A_{TM}$. If $R$ indicates $M$ writes symbol $``3"$ on the ...


2

In general, it is impossible to even determine if it will ever halt. And if it halts, determining the number of steps is also impossible. Check out the busy beaver game for details. There are general techniques that work in a large proportion of cases of practical interest, for a start check out the reference question here. But there have been complete ...


0

Suppose there exists $k>0$ such that $\lim_{n\to\infty} \left(3-\frac7n\right)=3-k$. By the definition of a limit, $$\lim_{n\to\infty} f(n)=L\Leftrightarrow \forall\epsilon>0,\exists N>0,n>N\implies |f(n)-L|<\epsilon$$ Here, we need to check: $$\lim_{n\to\infty} \left(3-\frac7n\right)=3-k\Leftrightarrow \forall\epsilon>0,\exists N>0,n&...


1

Both HP and MP are decision problems, namely sets of instances that you can think of as descriptive strings. For example, HP is a collection of pairs $M, x$ where $M$ is the description of a Turing Machine (think of a listing) and $x$ is an input to that machine. An instance is such a pair and a pair is in the set HP if the machine described by $M$ ...


2

I will assume that $g(G, v)$ computes a valid vertex cover, so it can never report a more optimal solution, and does so in polynomial time. We know that vertex cover is NP-hard to approximate within a factor below 1.36: http://annals.math.princeton.edu/wp-content/uploads/annals-v162-n1-p08.pdf. Since $g(G, v)$ reports a solution at most 5 more than optimal, ...


1

Search for Bellare and Goldwasser "The Complexity of Decision vs. Search" SIAM J. of Computing 23:1 (Feb 1994), pp. 97-119, or Bellare's class note on the matter.


0

You can recognize (but not decide) $L_1$ (essentially checking it ends "0", if so simulating $M$ on $x$ by a universal Turing machine $U$, otherwise reject). $L_2$ is essentially the complement of the language of $U$, which is not recognizable. $L$ is not recognizable. If it was, say by a Turing machine $R$, you could run $R$ in parallel over $\langle M, w,...


0

By contradiction. Suppose that for all $L_1$ undecidable and $L_2$ finite $\overline{L_1} \cap \overline{L_2}$ is decidable. Pick $L_1$ any undecidable language. The language $L_2 = \varnothing$ is certainly finite, it's complement is $\overline{L_2} = \Sigma^*$, so that $\overline{L_1} \cap \overline{L_2} = \overline{L_1}$, and that one isn't decidable if $...


0

Use nondeterminism. Given $M$, guess a string $w \in \mathcal{L}(M)$, simulate $M$ on $w$ (use your trusty universal Turing machine as a subroutine) and accept if $M$ accepts $w$.


0

By Rice's theorem, it is undecidable if $M$ accepts a language with a non-trivial property (there are languages that have the property and others that don't). "Includes a string starting 101" is a non-trivial property.


0

The answer to your question is yes. In 10 steps the Turing machine can consider at most 10 symbols, the set of strings of 10 symbols is finite. You can check each of them to see if the machine is still running after 10 steps in finite time. Be careful, Rice's theorem talks about properties of the language accepted by $M$, not directly $M$'s behaviour.


0

It is easy to see that if both $L$ and it's complement $\bar{L}$ are recognizable by Turing machine, they can be decided (copy the input to a new tape, then run the machines for $L$ and $\bar{L}$ in parallel, the first one to stop tells you what the answer is; by assumption at least one of them stops in finite time). So the possibilities are: $L$ and $\bar{...


0

The proof that Radò's function $\Sigma(n)$ (maximal number of 1 written by an $n$ state Turing machine starting on a tape of all 0s before halting) isn't computable is rather simple, once you have a few building blocks. First, by convention Turing machines start in state 1 and halt by moving to the (non-existent) state $n + 1$ (so you can build a machine ...


1

Another way to do it: Take any non-computable function $g(n)$, then the function defined as: $\begin{equation*} f(2^k (2 n + 1)) = g(n) \end{equation*}$ for all $k \ge 0$ satisfies your conditions.


3

Cook up some encoding of Turing machines so that if $n$ codes a machine, $2 n$ codes "the same" (perhaps use binary numbers ending in 1 as starting points, and 0s at the end are disregarded, thus making that odd $n$ and $n \cdot 2^k$ represent the same machine). Then use that e.g. $\operatorname{HALT}(M)$ (does $M$ halt if started on an empty tape?) isn't ...


2

A classic example of an uncomputable function is The Busy Beaver Problem: For each N, consider all N-state Turing Machines over the alphabet { [blank], 1 }; over all of those machines which always halt when started on a blank tape, find one which leaves the maximum possible number of 1's on the tape once it has halted; then f(N) is that number of 1's.


0

This is just an elaboration of the proof noted above. Consider the following algorithm: A(x) { Step 1: If x is not of the form $(M,1^{t})$ for some nondeterministic Turing machine $M$ and integer $t$, reject. Step 2: Compute $q = 2^{g(n)}$ where $n$ is the length of $x$. / * Needs $O(g(n))$ deterministic space, assuming $g$ is ...


1

The direction of reduction that you are asking for is a bit strange. Typically, we reduce from $A_{TM}$, in order to show undecidability. Perhaps you meant to ask about the other direction? At any rate, in answer to your question: your attempt was actually quite close, it just needs a bit of modification. Here's how you can proceed: Given $M_1,M_2$ as ...


1

The final m-config for the second configuration is an "e".


3

Using the proof of the Cook–Levin theorem, for every input $x$ you can construct in polynomial time a SAT instance $\phi(r,z)$ which encodes "$M$ accepts when run on input $x$ and randomness $r$". Here $r$ is a vector of $m = \mathit{poly}(n)$ bits, representing the random bits of $M$, and $z$ is an auxiliary vector, with the following property: in any ...


0

Do you mean "indeterministic" in the sense of quantum mechanics? It's easy to build that kind of indeterminism into a computer, by incorporating a routine that goes and checks the state of a quantum mechanical physical source. That doesn't necessarily violate the Church-Turing thesis, since the source of quantum mechanical randomness might not be the ...


3

Is it possible to make a machine that when it encounters a non-deterministic step it takes an arbitrary one? Yes easily. Will this machine be able to solve NP problems in P? No because it will most likely pick the wrong path through the execution. Similarly for outputting a number there is no way to force the machine to match the required path needed to ...


3

Suppose you had such a TM, namely a machine $M$ for which the problem was "Does $M$ halt on empty input?" Certainly that problem would be decidable: one of two algorithms must be correct, (1) Answer "yes" or (2) Answer "no". The fact that we might not know which one is the correct algorithm is immaterial here; the only thing that matters is that we're sure ...


0

Here's a way to construct a machine that computes $s_i$ from an input $p_i$ that has length $n_i$. It's based on @YuvalFilmus's very helpful answer and the proof of a related theorem by Satyadev Nandakumar, to which Yuval linked. I thought it might be useful to spell out the steps a bit further for anyone else interested in this question--at least, anyone ...


Top 50 recent answers are included