celtschk
Reputation
9,820
Top tag
Next privilege 10,000 Rep.
Access moderator tools
 Apr2 answered Why can one expect that $n\cdot p$ elements complete the test? Mar22 comment If $Q$ is orthogonal, $D$ diagonal, $QDQ^T=L^TL$, how to know $L$? With $O=Q$, $O^TQ=Q^TQ=I$ and the same for $Q^TO$. Now, $Q\sqrt{D^{-1}}Q^T = \sqrt{A^{-1}}$, so the result is the same solution you've found. Mar22 comment Showing a union of null sets is again a null set But unless the sets are disjunct, their probabilities generally do not add up, so $\le$ is IMHO the right thing to use (although in hindsight we also know that $=$ is right, too, because the r.h.s. is $0$, and a probability cannot be negative). OTOH, I see nothing guaranteeing that $P(\bigcup A_n)$ actually exists ($P(A_n)$ quite obviously is allowed not to exist, or else the whole subset construction would not be needed). But I also don't see that you actually need it. Mar21 comment base for finite dimensional vector space is not infinite dimensional vector space? Remember that linear combinations only have finitely many non-zero coefficients, even in infinite-dimensional vector spaces. Mar21 comment If $Q$ is orthogonal, $D$ diagonal, $QDQ^T=L^TL$, how to know $L$? The matrix is not unique. If $X$ is a matrix with $X^TX=Y$ and $O$ is an orthogonal matrix, then for $X'=OX$ we have $X'^TX' = (OX)^TOX = X^TO^TOX = X^TX = Y$. It should be obvious which orthogonal matrix you want to use in the definition of $F$. Mar21 comment Find equivalence classes of x ~ y : <=> x-y ∈ Z Just find a set $X$ which contains every decimal part just once; the equivalence classes are then uniquely given as $[x]=x+\mathbb Z$ for $x\in X$. Mar21 comment how to find coordinates of a point perpendicular to a line? @G-man: There's a reason why I ended that comment with a smiley. Mar21 comment how to find coordinates of a point perpendicular to a line? @G-man: Probably about the one that is parallel to the line $y=3x$ ;-) Mar21 comment how to find coordinates of a point perpendicular to a line? $P$ is the intersection of the two lines. Mar21 comment Limit using L'Hôpital's rule. Actually I would have interpreted $\ln^2(x)$ as $\ln\ln x$. Mar20 revised Is there a Linear Map to represent transpose? Added how the transpose may be written as more general linear function of the matrix Mar20 answered Is there a Linear Map to represent transpose? Mar18 comment Map that sends a $2x2$ matrix to a Mobius transformation is a homomorphism $\phi(B)=z\mapsto\frac{az+b}{cz+d}$. Or maybe I should write the (equivalent) $\phi(B)=x\mapsto\frac{ax+b}{cx+d}$ to avoid using $z$ again. Mar18 comment Map that sends a $2x2$ matrix to a Mobius transformation is a homomorphism If $B=\begin{pmatrix}a&b\\c&d\end{pmatrix}$, then $\phi(B)(z)=\frac{az+b}{cz+d}$. Mar16 comment Is there a Turing Machine that can distinguish the Halting problem among others? Good point, I didn't think of that. But that's also easily solved: Just have an oracle that only lies on halting machines, and another one that only lies on non-halting machines (and otherwise both have the properties discussed before). Then this reciprocal situation cannot occur. Either all algorithms which give different results do halt, or all algorithms which give different results don't halt, depending which of the two oracles is connected, and there's no way the Turing machine can decide which of the two is the case, as all with different results are such that the machine can't decide. Mar15 comment Is there a Turing Machine that can distinguish the Halting problem among others? … of the algorithms it can decide whether the algorithm halts, it could use those algorithms to test the oracles: If an oracle gives "Yes" for an algorithm known not to halt, it cannot be the halting oracle, and the same is true if the oracle gives "No" for an algorithm known to halt. Therefore our fake halting oracle must give the correct answer for all those algorithms the tested Turing machine can decide. But since the oracle is chosen only after knowing the Turing machine, that's not a problem; the set of algorithms it can decide is fixed as soon as the Turing machine is fixed. Mar15 comment Is there a Turing Machine that can distinguish the Halting problem among others? While a Turing machine cannot solve the halting pronlem for arbitrary code, it is possible to make a Turing machine that gives three results: "Halts for sure", "Runs forever for sure" and "Can't decide". As very simple example, it could give "Halts for sure" for the algorithm that halts immediately without doing anything, "Runs forever for sure" for the simplest infinite loop, and "Can't decide" for anything else. But more sophisticated algorithms will be able to successfully analyse more algorithms (but never all of them, as that would mean solving the halting problem). And since for some … Mar15 comment Is there a Turing Machine that can distinguish the Halting problem among others? OK, take as second oracle the following: For any algorithm where your Turing machine can by itself decide whether it halts or not, it gives the same answer as the halting oracle, and for any other algorithm, it gives the opposite answer. There's no way your Turing machine can distinguish that oracle from the true halting oracle: If your Turing machine can proof two algorithms equivalent, either it can decide both, or it can decide neither. It it can decide it, it cannot use that to distinguish the oracles because both give the same result. Otherwise, it has no information to distinguish them. Mar15 comment Is there a Turing Machine that can distinguish the Halting problem among others? So just choose as second oracle one that still gives the same answer for the padded machine (it may have access to a Turing machine equivalence oracle, after all). Mar15 comment Is there a Turing Machine that can distinguish the Halting problem among others? So oracle A gives "Yes", oracle B gives "No". The Turing machine adds an infinite loop, and both oracles give "Yes". So how is your machine to distinguish between (a) A is the halting oracle, i already doesn't halt, and B just happened to give "no" for i, and (b) B is the halting oracle, i does halt, and A just happened by chance to give "Yes" for i? Note that it could be that oracle A is "if the algorithm is i, give yes, otherwise consult the halting oracle", or it could be that oracle B is "if the algorithm is i, give no, otherwise consult the halting oracle".