Gondolin
Joined 8 years ago
Karma
115
Submissions
27
Member since
Sep 28
Recent submissions
Comment · 7 years ago
Comment · 7 years ago
The ultimate generalization is to use an inductive definition based on recursive ideals. For instance the fast growing hierarchy f_alpha: https://en.wikipedia.org/wiki/Fast-growing_hierarchy
Since ordinals are the ultimate recursion tool, any such function will ultimately grow faster than whatever recursive definition you can cook up by hand.
For instance even the slow growing hierarchy g_alpha, which grows very very slowly catches up to the fast hierarchy at extremely large ordinals.
Some examples:
- f_0 behaves like addition, f_1 like multiplication, f_2 like exponentiation, f_3 like tetration, f_w like Ackerman
- Graham number is bounded by f_{w+1}(64)
- Goodstein function behaves like f_{epsilon_0} (this show how much faster it grows than Ackerman). Similar for the Kirby-Paris Hydra
- n-Iterated goodstein behaves live f_{\phi(n-2,0)} where \phi is Veblen's function
- the tree function from Kruskal's tree theorem behaves like f_{\psi(Omega^Omega^omega}, ie by the small Veblen ordinal. And the graph function from the Robertson-Seymour theorem behaves like \psi(Omega_omega).
By contrast the slow growing hierarchy grows extremely slowly, for instance g_{epsilon_0} only grows like tetration. But it still catches up to the fast growing hierarchy at very large ordinals.
Comment · 7 years ago
Yes, Emmy Noether was a pure genius (one of the greatest mathematician of all time), and was never named full professor (even though she had Hilbert support).
Comment · 7 years ago
It would be nice to know the priority of blocking elements between firefox default anti-tracker list, ublock origin, and privacy badger.
When I see a tracker hit ublock origin does it mean that it bypassed firefox anti-tracker blocking, or is it the reverse?
Having three anti-trackers installed is also a bit inconvenient when this breaks a site, I have to disable each one successively to try to make it work again...
Comment · 7 years ago
Now that systemd-nspawn also has oci support, I wonder if podman/cri-o are going to switch to nspawn rather than runc.
Comment · 7 years ago
The Fibonacci example is interesting. If you want arbitrary precision, then the naive recursive method is exponential in $n$ to compute $F_n$. The loop method (recursive method with cache) is in $O(n^2)$. Indeed you only have $n$ steps in the loop, but at step $k$ you add $F_k$ and $F_{k+1}$ which have $O(k)$ bits so the total costs is $O(n^2)$. Finally the matrix/formal \sqrt{5} algorithm costs $O(n log n)$.
Indeed, using fast exponentiations, you only need $O(log n) matrix multiplications. But the dominant cost is actually at the last step, where you multiply two numbers of size $O(n)$ bits for a total cost of $O(n log n)$.
Speaking of mathematics in programming: I find it remarkable that the recent convergence of async programming into the use of promises and async/await (in python, js, rust...) is a weak form of the continuation monad. And the continuation monad is a form of the 'not not' Lawrere topology!
Comment · 7 years ago
On the other hand, constructive set theory is still rather a niche part of mathematics (this may change with the recent development of HOTT). It is hard not to use the LEM (and I am not good at it, I am not an expert on this subject. Expert say it gets easier over time to get used to not use LEM).
For instance, in the intuitionist reals, from "x >= 0 and x != 0" you cannot conclude that "x != 0". To prove x>0 you would need to exhibit a natural number n such that x>=1/n (so in other words you need a constructive proof that x>0). But this is not always possible, you have models of R where there is an x != 0 which is smaller than all the 1/n.
There is however one nice feature of intuitionist theory: every geometric sentence which is provable in classical theory is actually true in intuitionist theory. So if you have a geometric sentence (https://ncatlab.org/nlab/show/geometric+theory) you can use LEM in your proofs, the proof will still be valid intuitionally!
Comment · 7 years ago
Only speaking about arithmetic rather than full set theory: in (full) second order arithmetic theory all models of the natural number N are isomorphic (in a unique way). The big drawback is that this theory is completely undecidable, so we usually interpret it in first order logic set theory where it becomes incomplete. By Godel, you cannot have an arithmetic theory with decidable proofs and completeness.
In set theory one has to be careful that you can have models which are not transitive models. So Löwenheim-Skolem implies that if you have a model, you have a countable model. But you may not have a transitive countable model. However you do have a transitive version of Löwenheim-Skolem, by Mostowski collapsing lemma: "there exists a transitive model" <=> there exists a countable transitive model".
Comment · 7 years ago
More precisely the effective topos is a kind of realizability topos with a nno where every function is computable. Such a (non trivial) topos cannot be classical, otherwise the halting problem would be decidable. However the effective topos can only deal with calculability, not complexity. For complexity linear logic (without exponentials) and symmetric monoidal categories are better suited (but I don't know if there exists a model where every function is in P for instance).
Comment · 7 years ago
Oh yes, it is very much alive. For instance any topos (with a nno) is a model of intuitionist set theory. And since topos are a very natural type of categories (a topos= acategory which has finite limits and a power object), intuitionist logic is important in category theory.
Two examples: in algebraic geometry, mathematicians use schemes (introduced by Grothendieck), which have allowed to make tremendous progress. But from the point of view of intuitionist logic, a scheme is just a ring, and a quasi-coherent sheave is just a module over this ring (in more details they are ring objects and module objects in the big Zariski topos).
In synthetic differential geometry, one use a certain intuitionist topos to formalize intuitive aspects of reasoning with infinitesimal quantities (without relying on delta and epsilons). Note that non standard analysis also allows to work with infinitemismal quantities (by using ultraproducts), but has the same power has standard analysis (and in particular is classical). Synthetic differential geometry is intuitionnist, so is less powerful, but on the other hands its theorems are automatically valid for more models (complex models, formal smooth schemes...). In SDG, your reals R are a field with an (actually several) element epsilon !=0 (the infinitesimals) and such that epsilon^2=0 (that's why this only work in intuitionist logic, in classical logic R being a field would imply that epsilon=0). In this model every function f: R->R is differentiable, and we have f(x+epsilon)=f(x)+f'(x) epsilon.
In proof theory (like coq) one work with Martin Lof type theory, which is the type theory of topoi (and so is intuitionist). A recent development is to work with homotopy type theory instead, the type theory of \infty-topos. This is more powerful (and can be used as fundations for all of maths), and solve real problems, like correctly defining equality (equality is actually a tricky concept, for instance it may not be the case in the prover's theory that "for any two functions f and g such that forall x, f(x)=g(x); then f=g", but this is obviously a feature we want.) On the other hand it is quite a bit trickier to define (we need (infty,1)-categories).
Comment · 7 years ago
Some plants have a closed cooling system. And the million figure count fish eggs, which is somewhat cheating. And if you take into account the reduced wildlife area due to solar panel and wind farm needing more space than nuclear plants,
I stand by my statement that nuclear is more environmentally friendly per GWh (but I do concede that solar panels in desert and offshore wind turbines are even better than nuclear for the wildlife).
But in all this we should remember that environmental impact of fossil based electricity is an order of magnitude worse anyway.
Comment · 7 years ago
Again, a major accident would not take out half of Western Europe, this is fear mongering. A major accident would be severe, with a large exclusion zone and a lot of economic damage, but sill kill less than coal kill in Germany each year. And Germany was still constructing new coal power station in 2018!
I am not saying that Germany should invest in nuclear instead of renewable, but in nuclear along with renewable. And yes 15 years is a long time, but still a lot less long than 30 years (and Germany lost 10 years by being stubborn about nuclear).
And other countries that want to do a energy transition should not make the same mistakes as Germany. And political parties in France that want to close nuclear plants are environmentally severely misguided.
Comment · 7 years ago
No it is not zero CO2 output in 2050 but about 65% reduction only, or 80% if a 25% reduction of electricity consumption is achieved. This is 1) too late, 2) not even on par with France's electricity C02 production.
And a nuclear accident would not involve closing the whole country, it would involve an exclusion zone of 10-20 km (Fukushima exclusion zone is 20km, but it include zones where the residue radioactivity is <50 mSievert, way less than some natural radioactive places), a whole lot of economic damage (but negligible compared to climate change), and between 0 and (at worst) a few thousand deaths.
Comment · 7 years ago
Yes long term we should get rid of it (for fusion), but in short term the priority is climate change. And nuclear fision is a tremendous asset for climate change. There are still huge challenge of course, and we are unfortunately not at all on course to tackle them, but depriving ourselves of nuclear is only going to make things worse.
Comment · 7 years ago
I agree that Energiewende is important and that reducing the cost of renewable was sorely needed, but at the same time the decision to close the nuclear plants (rather than coal) was a gigantic mistake.
1) Because it costs a lot of lives. Coal + Lignite in Germany cost 8000 lives per year (funnily everybody also seems to forget that coal release more radiation in the air than nuclear plants). https://www.thelancet.com/article/S0140-6736(07)61253-7/abst...
By contrast Chernobyl was 4000 deaths https://www.who.int/mediacentre/news/releases/2005/pr38/en/
By not closing 10GW of nuclear production, Germany could have prevented 2000 deaths by year, so in total 20000 deaths over ten years.
2) Because it gave the impression that a carbon free electricity could be achieved by wind and solar alone. This is not the case: first Germany will only close coal in 2038 (in 20 years!!), and plan to use gas to replace coal at least up to 2050. Gas is way better than goal for air health, but it still release a lot of CO2. 2050 is way too late to be carbon free.
The problem with wind and solar is the intermittence: if you look at the data from https://www.cleanenergywire.org/factsheets/germanys-energy-c... you will see that on average wind is at 20% capacity and solar at 10% capacity. So even with batteries to smooth things out (which don't exist at the huge scale we are speaking with), Germany would need a lot more solar and wind that it does. For a peak consumption of around 70GW, this mean it would need 350GW of renewable energy. It is so far only at around 100GW, having added 50GW the last ten years. So at this speed it would still need around 50 years. This is without counting the fact that: - the energy stockage problem is at least as hard to solve - solar panel and wind turbines have a lifetime of 20 years, so this does not take into account replacing existing ones - it is getting harder and harder to find place to put them. In 2018 the rate of installation of new renewables slowed down a lot because of this problem.
3) By contrast nuclear cost less, when taking into account this intermittence problem and the cost of interconnection (which is not counted by the figures usually given); it is a lot easier to interconnect a huge centrale than a lot of small ones. But cost is not an argument anyway when we are talking about climate change (if there was a proper carbon tax at least Germany would have closed coal before nuclear).
It is friendlier to the environment (wind turbine kills a lot of birds, and solar panel take a lot of room from wildlife).
It is as safe as solar and wind, and way safer than hydroelectric and coal. Banqiao Dam collapse was 230000 deaths. Yet nobody is calling for stopping hydroelectricity.
Again, Chernobyl was "only" 4000 deaths (high range estimate using a linear model rather than a threshold model are at 10000-20000 deaths), Fukushima was 0 deaths (but 1500 due to the evacuation, including zones where the radiation was the same order of magnitude of the natural one). Chernobyl cannot happen with modern reactors; a Fukushima style incident could, but the nuclear operators increased the security of the points of failures that Fukushima revealed. Again, living near a dam is probably less secure than living near a nuclear plant. And building and installing solar panels and wind turbines cost lives too (as do building dam and nuclear plants, and so on); on average as much as nuclear killed. Yet there is a lot of hysteria about nuclear plants, because an accident is so much more spectacular and visible.
And yes an accident would leave an exclusion zone, but it would actually be smaller than this stretch of no man land (a coal mine in Germany): https://twitter.com/LejeuneXa/status/1124749045996634118
4) I am not saying nuclear fission is a miracle energy (fusion would be). It is as safe as it is in developed countries because of all the regulations, this model would not be applicable in developing countries. For these countries, wind and solar is the way to go, and in this respect Energiewende which paved the way is a success.
There is the problem of nuclear waste, but this frankly this is a (small) problem at the scale of 100s of years, this should not at all be our priority given the very small time frame we have to reduce climate change (the ship has unfortunately sailed for preventing it from being too impactful [aka more than a few million deaths], the real question is whether we limit it to be really impactful or a total catastrophe). This is like worrying about a leak in the sink when the whole house is on fire: bad priorities!
5) But, by making the illusion that 100% carbon free electricity could be achievable without nuclear, Germany set a dangerous precedent. It is not currently possible (as proved by Germany not really reducing its CO2 emissions), it may be possible in 30 years (current prevision is only a cut of 65% in 30 years, the 95% cut is from a very optimistic plan by Greenpeace) but this is way too late.
By refusing to use nuclear for purely ideological# reasons, Germany is depriving itself from a vital tool against global warming. And by vindicating some green movements to call for the closing of nuclear plants along the development of renewable (whereas the sane thing to do would be developing nuclear along renewable: solar panel in sunny places like desert, offshore wind turbines and nuclear plants), it may indeed have done a whole lot of harm. And when we are speaking about the future of human civilisation, this may prove to have been indeed a very costly mistake indeed.
[#] And yes, when you take into account that coal each year kill more in Germany than Chernobyl did globally (and way more than Fukushima); and that even if there was a Chernobyl every 10 years (which cannot happen with the nuclear reactors we have) anyway it would still be a drop of water compared to what climate change is going to bring us, closing nuclear plants can only be ideological.
By "ultimate generalisation" I was speaking about a family of computable functions that ultimately grow faster than other functions you could cook up by hand: you put all the recursivity in the ordinals, they are there for that, and logicians are very good at constructing very large (recursive) ordinals.
If you just want a very very fast growing function (but that is still computable, unlike busy beaver), you can do the a light busy beaver version: Beaver(N)=the maximal output of all turing machines T with N state where there is a proof in ZFC of length <=N that T terminates.
This function grows much faster than the other functions I described (basically it is a f_{ordinal consistency of ZFC}. If you are interested in this kind of ideas, there is this reddit post that develops these ideas: https://www.reddit.com/r/math/comments/283298/how_to_compute...