New answers tagged

5

Nice question! I think that your notion of an "effectively computable reduction" is interesting and worth studying, but not as fundamental as standard reductions. Let me provide some observations about this notion that may be illuminating: Observation 1: it does not make sense to talk about effectively computable reductions from one language to another; ...


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 ...


3

Metric TSP is NP-complete - hence yes, assuming you can solve the metric TSP in $6(n^{12})$, this is good enough to prove $P=NP$. Giving a blackbox that can do that, would be a quite strong evidence (if it actually works). But there are some considerations one should take into account: it actually could be somewhat dangerous, as someone else could figure ...


0

In POSIX ERE (extended regular expressions) you can write ^([a-z]*)\1$ (here (...) captures a match, which is repeated by \1 later, ^ matches the beginning of a line, $ it's end), which represents the language $\{\omega \omega \colon \omega \in \Sigma^*\}$ (the alphabet being lowercase letters), which isn't even context free.


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&...


2

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 could do it by making the second parameter of your function function like the index of the summation, and recursively increment this parameter as long as $0 \leq i < n$. $$f(n, i) = \begin{cases} 1 & \text{if } n =0\\ f(i, 0)\cdot f(n-i-1,0) + f(n, i+1) & \text{if } 0 \leq i < n\\ 0 & \text{otherwise}\\ \end{cases}$$ Then $...


0

If you apply the recursive formula again to $T(n/2)$ you get the following: $$ T(n) = \sqrt{2}\cdot T(n/2) + \sqrt{n} \\T(n)= \sqrt{2}(\sqrt{2}\cdot T(n/4) + \sqrt{n/2}) + \sqrt{n} \\T(n)= 2\cdot T(n/4) + 2\sqrt{n}$$ For this formula you are now probably able to draw a recursion tree.


4

Once you have proved that $|x-2^y|=0$ is a decidable predicate, the function $$\log_2(x) \equiv \mu y(|x-2^y| = 0)$$ should match the description of the function given and proves that it is recursive. Edit: To show that $|x-2^y|=0$ is decidable, show that $\overline{\text{sg}}(|x-2^y|)$ is recursive, which requires you to show that $|x-z|$, $2^y$, and $1 - \...


0

Use the power of nondeterminism: Guess $k$ strings of the form $a^* b^*$, check that $M$ accepts all of them. So your language is r.e. The property "contains at least $k$ strings of the form $a^* b^*$" is certainly not trivial, so your language isn't decidable by Rice's theorem.


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

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.


2

Here is a specific example, POSIX EREs (Extended Regular Expressions). POSIX EREs have, on top of the computer science definition, back-references for the first 9 capturing groups. This gives some extended properties, like being able to match the $a^nba^nba^n$ via the regex \(a*\)b\1b\1, which cannot be matched by any context-free grammars. However, POSIX ...


2

A famous example: a PCRE that finds primes. I couldn’t find Abigail’s original, but there have been many iterations on this. In JavaScript, for example, you can pass a function to the matcher to do arbitrary computation with the results.


1

In programing languages, or their libraries, functions for handling regular expressions are not interested in languages, they are interested in detecting things. For example, take the text of an e-mail and detect a phone number inside it. There is no reason to restrict regular expressions to those in computer science. For example, $a^n b^n$ is not a ...


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 ...


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 ...


Top 50 recent answers are included