Hot answers tagged

2

What the question asks is not what you probably mean, since $$ \lim_{n\rightarrow\infty}n^{x}=\lim_{n\rightarrow\infty}x^{n}=\infty\text{ for }x>1. $$ What you probably care about is $$ \lim_{n\rightarrow\infty}\frac{n^{x}}{x^{n}}=0\text{ for }x>1. $$ In other words, $n^{x}$ is in $O(x^{n})$. See if you can prove this.


2

This subject is known as formal verification in computer science, and people have done a lot of work in it. For a sufficiently general version of the question, and with a reasonable notion of proof, the answer is no. Any notion of proof $T$ to which the incompleteness theorems apply suffers from the following limitation. Suppose we write down a Turing ...


2

I expect that there are quite a few people on this site (myself included) who have earned degrees in mathematics and computer science at separate times and have experience both with the "just in time" learning and covering things far in advance of applying them. Even if you do a complete undergraduate math degree before getting seriously into CS, I believe ...


1

The general method is to convert the two regular expressions to a finite automaton each and compare those. In detail: Convert a regular expression to a non-deterministic finite automaton (NFA), e.g. via Thompson's construction Convert a NFA to a deterministic finite automaton (DFA) via power set construction Apply DFA minimization to a given DFA to get a ...


1

I am not exactly sure if this is what you are looking for but a simple example could look like a propositional calculus where we remove modus ponens (the only inference rule) to get an incomplete system. In such system, given a sentence $\varphi$, one could "semantically prove" $\varphi$ to be true by exhibiting an exhaustive truth table. Another example ...


1

If in the long run $\log_2 f(n)\lt \log_2g(n)+c$ for some constant $c$, then in the long run we have $$2^{\log_2 f(n)}\lt 2^{\log g(n)+c},$$ or equivalently $f(n)\lt 2^c g(n)$, that is, $f(n)=O(g(n))$.


1

You can find many explanations of the IEEE-754 format on the Web. In short, each 32-bit single-precision floating-point number consists of three parts (we assume that the bits numbering begins from zero): sign, bit 31 exponent, bits 30-23 (eight bits in total) significand (or "mantissa"), bits 22-0 (twenty three bits in total) However, in your case the ...


1

HINT: If $p$ is the pumping length, start with $s=0^p10^p1$ and pump down.



Only top voted, non community-wiki answers of a minimum length are eligible