Timeline for Proof there is no algorithm to compute the intersection of a line and sinusoidal wave?
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 11, 2017 at 19:09 | vote | accept | Jérôme Verstrynge | ||
| Dec 10, 2017 at 23:24 | comment | added | Loïc Teyssier | @RobertIsrael Yes, you're probably right, I was a bit over-enthusiastic there. I very rapidly took $z:=ix$ and $w:=\frac{c}{2}(\exp(2ix)-1)$, which transforms $x=c\sin(x)$ into $z\exp(z)=w$. But of course $w$ depends on $x$ so my argument is moot (I lazily hoped that some quadratic equation with coefficients expressible in terms of $W$ would somehow pop out and save the day :D). That being said, the main part of my comment remains. | |
| Dec 10, 2017 at 23:20 | answer | added | Timothy Chow | timeline score: 15 | |
| Dec 10, 2017 at 20:08 | comment | added | Robert Israel | @LoïcTeyssier AFAIK $z = c \sin(z)$ is not at all equivalent to $w = z \exp(z)$ and can't be done in "closed form" using Lambert W. However, I think very little is known about closed form solutions for transcendental equations. | |
| Dec 10, 2017 at 17:28 | comment | added | Goldstern | "recursive functions" in your sense are usually defined on the integers, or on some other set which comes with an enumeration. Not on the reals. | |
| Dec 10, 2017 at 15:17 | comment | added | Jérôme Verstrynge | I am referring to mathworld.wolfram.com/RecursiveFunction.html for which an answer is provided for any input (which makes them total as opposed to partial when they don't provide an answer for all possible inputs). I consider your equations as solvable by symbolic manipulation since I can transform them into x = ln(2) and x = sqrt(2). Of course, one will argue that the solution is an irrational number and we never get the exact value of these solution since their numerical representation is infinite. We need an iterative algorithm to figure the value with arbitrary precision. | |
| Dec 10, 2017 at 14:52 | comment | added | Goldstern | It is not clear what you mean by "total recursive" (in the context of real numbers). It is not even clear to me whether you consider the equations $e^x=2$ or even $x^2=2$ "solvable by symbolic manipulations". Which symbols do you allow? | |
| Dec 10, 2017 at 14:51 | vote | accept | Jérôme Verstrynge | ||
| Dec 11, 2017 at 19:09 | |||||
| Dec 10, 2017 at 14:50 | comment | added | Jérôme Verstrynge | Well, the kind of formulas I am interested in are total recursive formulas for which only real solutions are of interest. I get your point about setting the formal framework. I will write another question. | |
| Dec 10, 2017 at 14:35 | comment | added | Loïc Teyssier | Yes, I secretly understood what you meant ;) My point was to underline the fact that depending on the choice of the type of formula you allow, different outcomes arise (my comment is still valid for your modified sine equation). For instance, why should it be felt legitimate to obtain «exact» solutions in finitely many steps in terms of $\log$ and $\exp$ and not in terms of other special functions? What if you allow only rational formulas? Joel's answer below gives a precise reference to the fact that defining properly the formal framework you work in is of paramount importance. | |
| Dec 10, 2017 at 14:24 | comment | added | Jérôme Verstrynge |
I should have written ax = sin(x) where a is any positive real. I was only thinking about real solutions when I wrote my question. I could have chosen another example. Iterations are performed until a threshold of quality is reached around the intersection. I was wondering about mechanical, step-by-step, resolutions, like that of resolving a set of linear equations.
|
|
| Dec 10, 2017 at 14:20 | review | Close votes | |||
| Dec 10, 2017 at 18:11 | |||||
| Dec 10, 2017 at 14:06 | answer | added | Joel David Hamkins | timeline score: 15 | |
| Dec 10, 2017 at 14:03 | comment | added | Loïc Teyssier | I can solve symbolically the afore-mentionned equation: the only real solution is $0$. Do you mean to solve it on $\mathbb C$ ? In which case, I guess it is equivalent to solving $w=z\exp(z)$ for some special $w$. The general equation is known not to be symbolically invertible using formulas in $w$, $\log(w)$ and $\exp(w)$ (look for Lambert function). So, I'd advise you to give a more detailed question regarding the kind of symbolic formula you're after, because I'm confident there exists symbolic formulas involving Lambert functions (I may be wrong, though). | |
| Dec 10, 2017 at 13:48 | review | First posts | |||
| Dec 10, 2017 at 14:05 | |||||
| Dec 10, 2017 at 13:47 | history | asked | Jérôme Verstrynge | CC BY-SA 3.0 |