New answers tagged computability
0
The algorithm to compute $G'$ is really easy: just return $G$.
Indeed, given any $G=(V,E)$ the only graph $G'=(V, E')$ such that $U \subseteq V$ is a vertex cover of $G$ iff $U$ is a vertex cover of $G'$ is $G$ itself.
To prove this you can show that we must simultaneously have $E \subseteq E'$ and $E' \subseteq E$.
Proof that $E \subseteq E'$: Suppose ...
1
Im assuming the OP meant the question is $(\forall M. M \text{ is nondeterministic polynomial TM }, L(\overline{M})\in P) \iff P=NP$.
Look at Steven's answer for the solution regarding the other interpretation of this question.
This proof assumes $\overline M$ is a TM that accepts $(w, x)$ where $w$ is a witness for $x $, iff $M$ rejected $(w,x)$. This does ...
0
Problem: Is a = b?
Reduction to bin packing: Assume you have bins of size (a+b)/2. Can one item of size a and one item of size b be packed into 2 bins?
We just reduced a very, very simple problem to an NP-complete problem.
1
Let's imagine a Non Deterministic Turing Machine $M$ that decide $SAT$. If we tune this machine a bit, and add a transition on the initial state, for every letter read, that reject the entry. Let $M'$ be the new NTM. Then, $L(M') = L(M)$, since $u\in L(M) \Leftrightarrow \exists$ at least one computational path in $M$ to an accepting state (and the same ...
3
A lot of confusion arises because the sloppy notation and imprecise terminology involving free and bound variables. Let me try to clear some of it up.
The title of your question wrongly claims that $\forall x \in \mathbb{N} \,.\, \Phi(x,x)$ is a function, which it is not. It is a truth value. Let us see why this is the case.
Suppose someone defined $f$ by ...
1
Suppose that all problems in the world could be ranked in terms of difficulty, where higher numbers correspond to more difficult problems.
If $B$ is NP-hard then its ranking is large, $r(B) \geq M$.
If $A$ reduces to $B$ then $A$ is not harder than $B$, that is, $r(A) \leq r(B)$.
Given $r(B) \geq M$ and $r(A) \leq r(B)$, can you conclude any lower bound on $...
2
B being NP-hard does not say anything about A. The problem says that there is a way to reduce A to B in polynomial time.
But on the other hand, it is also not given that A getting reduced to B is the only pathway for solving A. So, there can be other ways of solving A in polynomial time.
Hence, the implication that A is NP-hard is false.
1
In the general case, this is undecidable, and it turns out the answer has nothing to do with being rational or irrational.
Consider a Turing Machine with state set $Q$ with a single halting state $H$. Let's define $isHalting(H) = 1$ and $isHalting(q) = 0 $ for $q \neq H$. Define $state(n,w)$ to be the state of the Turing Machine starting on input $w$ after $...
5
What you're misunderstanding is how "problem" is used in computer science. "Problem" does not refer to finding the correct output for a particular input, but writing an algorithm that returns the correct output for all inputs. For instance, is there an algorithm that sorts a list in linear time? You could write a program that simply goes ...
3
No. Any such machine $T^*$ would allow you to immediately solve the halting problem.
Given a description of $M$, construct a Turing machine $T_M$ that simulates $M$ and then outputs some fixed string, e.g., "0". Notice that, given $M$, $T_M$ is computable.
Then $T^*$ with input $T_M$ and "0" accepts if $M$ halts and rejects if $M$ does ...
4
No, in fact any non-trivial semantic property of Turing machines is undecidable. This result is Rice's theorem.
1
So, Captain Kirk tells the android that Harry Mudd is a liar. Everything he says is a lie. The android accepts this premise, whereupon Harry Mudd says, "I am lying." The android expresses confusion that Mudd cannot be lying b/c that would be true and that cannot be true b/c he is a liar. Smoke comes out of his ears and Kirk saves the day! This is ...
2
I find postings above saying a computer can decide the truth or falsity of some statements but not of some others.
I find that a somewhat misleading way of putting it. For statements in first-order logic, a computer can search for a proof and if one exists it will find it. But if the program has been running for a trillion years and hasn't yet found a proof, ...
3
The computability-based generalized incompleteness theorem with its proof would shed more light on your question. In particular, Yuval's answer states but does not prove that the set of true arithmetical sentences (true according to the standard model $(ℕ,0,1,+,·)$ of PA) is undecidable. The linked post shows via reduction to the halting problem that the set ...
2
Other people have covered explaining the actual meaning of the theory this paragraph referenced. I will instead address how the quoted paragraph was intended to be interpreted, such that it does in fact correctly describe the theory.
During the first half of the twentieth century, mathematicians such as Kurt Godel, Alan Turing, and Alonzo Church discovered ...
0
You can write a computer program that will prove / disprove some mathematical theorems. There are some problems that can be solved very easily but need an enormous number of steps to solve; computers can handle them easier than humans. For example the statement “1526753673279839 is a prime” is no big deal for a computer.
But there are two problems. One is ...
3
We give a Turing reduction from the $\mathrm{SubsetSum}$ problem.
Suppose we are given a $\mathrm{SubsetSum}$ instance $(A, k)$ where w.l.o.g. $A$ only contains positive integers, i.e. we want to find a set $X \subseteq A$ such that $\sum_{x \in X} x = k$ and define the set $A' = A \cup \{- k\}$.
We want to show that $f(A') = 0$ if and only if $(A, k) \in \...
2
Consider this version of the halting problem: given $T$, decide whether $T(\varepsilon)$ halts (where $\varepsilon$ denotes the empty string).
Let $\overline{0}$ (resp. $\overline{1}$) be the string containing $101$ zeros (resp. ones) and suppose towards a contradiction that your function is computable. Then, given $T$ you can construct a Turing machine $M_T$...
2
Since for a given $n$, there are only finitely many strings in $\Sigma^n$, saying "run $M$ on all words from $\Sigma^n$" does make sense. But we need to be somewhat careful about the details here.
We could run $M$ on all $w \in \Sigma^*$ in parallel. If we do that, then (assuming that $M$ halts on at least one of them, which we may do here), there ...
7
The statement is overly broad, as well as being overly complimentary to people. Computers can’t solve all problems but neither can people. Not sure why the extra drama was added.
What that is referring to is basically an aspect of the Halting Problem. A Turing machine can determine the answer to some questions but is unable to do so for others. They even ...
5
A simple example of undecidable mathematical statements are whether multivariate integer polynomials have natural roots.
This means that we an expression $E(n_0,\ldots,n_k)$ built from natural number constants, natural number variables $n_0,\ldots,n_k$, addition, substraction and multiplication. We then want to know whether a solution for $E(n_0,\ldots,n_k) =...
2
Suppose that the longest word in the language has length $m$. The Turing machine reads the first $m+1$ symbols on the input tape. Based on that, it can decide whether the input belongs to the language or not. This Turing machine runs in constant time.
29
On top of what everyone else has said, it may be worth talking about where some of the boundaries of decidability and undecidability are.
For natural numbers:
The first-order theory of natural numbers with only addition (Presburger arithmetic) is decidable.
The first-order theory of natural numbers with only multiplication (Skolem arithmetic) is decidable.
...
1
Look at the time hierarchy theorem for an explanation. In particular, we know (using this theorem) that $P\subsetneq E\subsetneq EXP\subsetneq R$, and we could have added a lot more complexity classes in between them.
12
The key is quantifiers, both in the theorem, and in the "mathematical statements."
First, the theorem says that "there is no algorithm that can take in an arbitrary mathematical statement and prove if it is true or false." This does not mean that, for every mathematical statement, a computer can't determine if it's true or false. It just ...
71
The claim is not that a computer cannot determine the validity of some mathematical statements. Rather, the claim is that there is a class $\mathcal{C}$ of mathematical statements such that no algorithm can decide, given a statement from class $\mathcal{C}$, whether it is valid or not.
The standard choice for the class $\mathcal{C}$ is statements about ...
3
They are not precisely the same language. For instance, $\overline{SAT}$ has words that are not even formulas. $UNSAT$ on the other hand, has only formulas that are not satisfiable.
In terms of complexity measures - the two languages are equivalent, since we can check in polynomial time whether a given input word is a formula or not and therefore we have a ...
2
The language is in RE: simply generate all inputs $x$ with $|x|\le 10000$ (they are finitely many), and simulate $T$ on all inputs in parallel. Whenever one simulation halts, accept.
The language is not in co-RE, as otherwise it would be decidable and we could solve the Halting problem.
Indeed, to decide whether a Turing machine $T$ halts on empty input, we ...
0
The problem isn’t that computers, being limited by the real world, cannot implement a Turing-complete machine. The problem in this question here is that the C language itself doesn’t allow it.
The C language could easily be changed to be Turing complete. Adding an integer type of unlimited size that can be used in malloc() and in pointer arithmetic would ...
0
Mapping "C" to a Turing equivalent abstract model of computation
The basic syntax and semantics of C could be mapped to an abstract model of computation that is Turing equivalent. The RASP model of computation is a model that "C" can be mapped to.
A variation of the RASP model is shown below that the x86/x64 language maps to. Since it is ...
1
You say
$\langle M \rangle$ should accept all the inputs, and if one of the inputs rejected it's not $L(M)=\Sigma^∗$.
The above two statements are true, but you are not handling all behaviors of $M$.
In particular you are not considering that $M$ could never halt on some input $x$. In that case $L(M) \neq \Sigma^*$.
In short, your observation do not imply ...
3
Your suspicion is correct. Without primitive recursion we get a very small class of functions, namely maps of the form $f(\vec{x}) = x_i + m$, possibly with some undefined values.
Let $\mathcal{F}_k$ be the least class of partial maps $f : \mathbb{N}^k \to \mathbb{N}$ closed under $0$, successor, projections, composition and minimization.
Theorem: For every ...
0
Suppose that $f(x) = 0$. Then $g(f(x))$ is computable for any function $g$, computable or not. This explains 1.
As for 2, the composition of two computable functions is computable, so if both $f$ and $h$ are computable, so is $g$. Since $f$ is computable and $g$ isn't, the only conclusion is that $h$ is not computable.
2
It is called contraposition :
$f(x) \in B \Rightarrow x \in A$
is equivalent to
$x \notin A \Rightarrow f(x) \notin B$.
So, the two statements that you have seen are equivalent as well.
1
Your question is a bit unclear, but let me hazard a guess. Let $L$ be an NP language. According to the Cook–Levin theorem, there is a polynomial time reduction $\phi_L$ from $L$ to SAT, that is, $\phi_L$ is a polynomial time function that satisfies $x \in L$ iff $\phi_L(x) \in \mathrm{SAT}$. You are asking why $\phi_L$ is injective.
Roughly speaking, $\phi_L(...
4
Usually, when we talk about the complement of a set we have some reference set to compare to.
In the setting of languages over some alphabet $\Sigma$, this means that the complement of some language $L$ would be $\overline L = \Sigma^\ast \setminus L$, i.e. the set of all strings over $\Sigma$ which are not in $L$.
In the particular case of
$$\mathrm{Sat} = \...
Top 50 recent answers are included
