Let me offer one reason and one misconception as an answer to your question. The main reason that it is easier to write (seemingly) correct mathematical proofs is that they are written at a very high ...

You have at least two options, depending on what problem you want to solve. If you want innocent readers of your code to not get the answers inadvertently, or you at least want to make it a bit ...

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

It is known that P$\subseteq$NP$\subset$R, where R is the set of recursive languages. Since R is countable and P is infinite (e.g. the languages $\{n\}$ for $n \in \mathbb{N}$ are in P), we get that P ...

Hint: The search x AND y will result in 10 000 hits.

You are asking several different questions. Let me briefly answer them one by one. What is so important about the Turing machine model? During the infancy of computability theory, several models of ...

Consider the following grammar for arithmetic expressions: $$X \to X + X \mid X - X \mid X * X \mid X / X \mid \texttt{var} \mid \texttt{const}$$ Consider the following expression: $$a - b - c$$ ...

Consider the triangle graph with unit weights - it has three vertices $x,y,z$, and all three edges $\{x,y\},\{x,z\},\{y,z\}$ have weight $1$. The shortest path between any two vertices is the direct ...

Because asymptotic notation is oblivious of constant factors, and any two logarithms differ by a constant factor, the base makes no difference: $\log_a n = \Theta(\log_b n)$ for all $a,b > 1$. So ...

Here is an algorithm for the identity function: Input: $n$ Check if the $n$th binary string encodes a proof of $0 > 1$ in ZFC, and if so, output $n+1$ Otherwise, output $n$ Most people suspect ...

There are many ways to see this. One is a truth table. Another is to use the distributive rule: $$A \lor (A \land \lnot B) = (A \land \top) \lor (A \land \lnot B) = A \land (\top \lor \lnot B) = A \... View answer Accepted answer 46 votes SAT was the first problem shown to be NP-complete, in Stephen Cook's seminal paper. Even nowadays, when introducing the theory of NP-completeness, the starting point is usually the NP-completeness of ... View answer Accepted answer 44 votes You're mixing up computability theory (also known as recursion theory) and complexity theory (or computational complexity). Computability theory is a vast mathematical subject which studies the ... View answer Accepted answer 43 votes An algorithm is polynomial (has polynomial running time) if for some k,C>0, its running time on inputs of size n is at most Cn^k. Equivalently, an algorithm is polynomial if for some k>0,... View answer 41 votes Polynomial time algorithms are algorithms whose running time increases by a constant factor when the input is doubled in size. Exponential time algorithms are algorithms whose running time increases ... View answer Accepted answer 41 votes Your suspicion is correct. The CPU doesn't care about the semantics of your data. Sometimes, though, it does make a difference. For example, some arithmetic operations produce different results when ... View answer 40 votes No, there will be absolutely no implication, for several reasons: The P vs. NP problem is about classical computation rather than quantum computation. Even if quantum computers could solve NP-hard ... View answer 40 votes While it is true that the computation of a quantum Turing machine is vastly different from that of a classical one, nevertheless quantum Turing machines can be simulated on a classical Turing machine, ... View answer 39 votes All pseudorandom generators that don't rely on outside randomness and use a bounded amount of memory are necessarily ultimately periodic since they have finite state. You can think of them as huge ... View answer Accepted answer 39 votes Computer science is a misnomer - there is actually no "science" in computer science, since computer science is not about observing nature. Rather, parts of computer science are engineering, and parts ... View answer Accepted answer 37 votes Sage is an open source computer algebra system. Let's see if it can handle your basic example: sage: sqrt(3) * (4/sqrt(3) - sqrt(3)) 1 What is happening under the hood? Sage is storing everything as ... View answer Accepted answer 36 votes The usual meaning of algorithm is a program that always halts. Under this definition, no algorithm has a running time of \Theta(\mathit{BB}(n)), or indeed \Omega(\mathit{BB}(n)). Indeed, such an ... View answer 36 votes On the contrary. At the same time that hardware is getting cheaper, several other developments take place. First, the amount of data to be processed is growing exponentially. This has led to the ... View answer Accepted answer 35 votes It isn't true that every DFA for this language is non-planar: Here is a language that is truly non-planar:$$ \left\{ x \in \{\sigma_1,\ldots,\sigma_6\}^* \middle| \sum_{i=1}^6 i\#_{\sigma_i}(x) \...

It is impossible. Suppose that you have the result of all comparisons except for the pair $(i,i+1)$. Then you wouldn't be able to distinguish between the following two cases:  1,2,\ldots,i-1,i,i+1,i+...

For any given string there is a compression scheme that compresses it to the empty string. Hence it is not meaningful to ask how much a single string can be compressed, but rather how much a ...

There is no such thing as "the fastest growing function". In fact, there is even no sequence of fastest growing functions. This was already shown by Hausdorff. Given two functions $f,g\colon \mathbb{N}... View answer 34 votes Every recursion can be converted to iteration, as witnessed by your CPU, which executes arbitrary programs using a fetch-execute infinite iteration. This is a form of the Böhm-Jacopini theorem. ... View answer 32 votes We won't necessarily see any effects. Suppose that somebody finds an algorithm that solves 3SAT on$n$variables in$2^{100} n\$ basic operations. You won't be able to run this algorithm on any ...