We're going to build an exact copy of Ponyville... right over there! We've got less than a minute!
Twilight is Best Pony6,371 stories ·3,071 members
LessWrong64 stories ·316 members
Starswirl the Bearded183 stories ·234 members
Stories on Goodreads28,599 stories ·492 members
Starlight Glimmer2,901 stories ·1,539 members
Sunburst159 stories ·256 members
The StarBurst Trashbin (Starlight/Sunburst)205 stories ·70 members
Starlight believes she's broken magic itself. Worse, she can prove it. And she's going to need help from her closest friends... because her entire life has been leading up to this moment...
Set between Seasons 7 and 8. Warning: contains recursion, self-reference, and higher-order spells. Plus flashbacks and didacticism. And Starlight being Starlight, of course...
Page generated in 0.133 seconds
Total duration
714 users online
772,364 hits today, 2,280,440 yesterday
My Little Pony: Friendship is Magic Fanfiction
Designed and coded by knighty & Xaquseg - © 2011-2024
Support us
SubStar
Chat!
Discord
Follow us
Twitter
MLP: Friendship is Magic® - © 2024 Hasbro Inc.®
Fimfiction is in no way affiliated with or endorsed by Hasbro Inc.®
And this story will be written, when? Come on. Somepony needs to have it happen. I've got too much else to do to write it myself.
"And Starlight being Starlight, of course..."
Why do I see so many comments hating Starlight for just being Starlight? Lol
10565416
It was meant in a good way, actually, like Twilight Twilighting, which is endearingly, enjoyably discombobulated...
Beautiful. However I'm still not sure I quite understand what Starlight's proof exactly was. Was it "any system of magic can't be proven to be rock solid through automatic means, because the spell that checks it can't verify itself?"
10565498
It's an analogy to Gödel's incompleteness theorem, which is basically that in any consistent formal logic there must exist statements that are true, but cannot be proven true. One can certainly imagine a formal system in which all true statements are castable spells, but I found the story's premise to be a bit of a stretch, because practially you would not be limited to proving the existence of spells using just that system; it would be ok to create a metasystem (reasoning about the first system) where not all true statements are castable spells, but all castable spells are provable. Still, a cute story.
10565498
Here's the computer version that might help you follow this.
10565498
Credit where it's due, Starlight's proof is "inspired by" a famous result in logic, Gödel's First Incompleteness Theorem, which shows that any sufficiently powerful axiomatic system for deriving mathematics from logic cannot be consistent or complete.
In a nutshell, you can represent theorems as immensely huge numbers (or in pony magic, as the "unrolled" forms of spells) and derivations of proofs by even larger numbers, and then represent the operations of the logical system itself as relationships between these numbers. This allows the system to "talk about itself" by its own derived theorems, which leaves it vulnerable to self-referential statements like "the statement represented by the number g is not derivable in this system", where g is the number of the statement itself. It's not a problem with G, it's just that any system powerful enough to talk about itself will eventually hit its own version of the Liar Paradox, "I am lying", and be shown to be incomplete.
In a way, Starlight is in the role of Gödel here, and Sunburst is Russell & Whitehead (authors of Principia Mathematica, the prototypical example of such a system, which takes upwards of 700 pages to show that 1+1=2). With Star Swirl, perhaps, in the role of Hilbert, who posed axiomatization of mathematics as an important problem to be solved, though I didn't go into that here.
It's a cool result, though it kind of feels like it "breaks" mathematical logic, which is where the idea for this story comes from. I'm also borrowing a bit from Turing's demonstration, that no program can determine whether or a program will "hang" indefinitely, since spells in the pony world are somewhere between mathematical statements and computer programs. But ultimately it comes down to the same thing: self-reference is a bear-trap if you want mathematically solid guarantees...
10565606
I've recently studied subjects somewhat related to that: set theory and function complexity, and I have a vague idea of that theorem...
Still gives me a headache.
10565640
Read Gödel, Escher, Bach, sometime -- it was my introduction to this, plus a lot of related topics...
This is so adorable that it hurts. A little too relatable, too.
10565650
What about making a singularity spell?
A spel that when active continually makes every position combination of the spell chunks it has and that Absorbs and disassembles any spells that come in contact with it and just keeps growing
10565681
That's the Gray Goo spell, really... and there's a reason why the only known copy of it is locked in a magic-proof vault in the Secure wing of the Archives, under a sign that says simply "No. Don't even think it."
The Singularity spell is the one where you finish writing it and suddenly, for no reason
10565697
The universe crashes,
Now imagine a computer programming version
A program designed to make, archive, and run every possible string of binary code, so
0 1 00 01 10 11 000
And so on
10565701
That's the Borges' Infinite Library spell. And the sad thing about it is, every possible perfect program is included in the results, but good luck finding them. Because every program with one bug is included, and every program with two bugs, and so on. Plus every possible program that you are head-pounding-on-the-table certain must work, and for a reason you can't ever possibly see simply doesn't, that's in there too. (A lot of those have semicolons in them.)
And that's only the merest sliver of rationality in the dross. 99.9999999999% of the remaining programs don't run at all.
And the remaining 0.0000000001%? That's the Internet...
10565720
What would it do to what ran it?
10565726
Well nothing, since you're clearly assuming an infinite-tape Turing machine...
10565786
No? I meant all combinations are stored digitally so the program can run checks so it doesn’t repeat
A wonderful story, and the logical progress of the thesis felt really good too. Solid stuff.
I think there's something missing in the proof. It seems to me that
G(S,g)could be derivable inSand simply returnfalse. I'm not particularly familiar with Gödel's incompleteness theorem, but the proof of the halting problem has a step that I think is missing here. GivenH(x,y), which returnstrueexactly whenxhalts on inputy, we constructf(x) = if H(x,x) then DIVERGE else HALT, and considerH(f,f). The important point is that the halting status off(x), not just the return value off(x), depends onH(x,x). It's not enough to definef'(x) = ~H(x,x), since in that case we just get thatH(f',f') = true(f'halts on all inputs becauseHhalts on all inputs) andf'(f') = false.This might work out differently if
Gwas a theorem, but it sounds like here it's a function: "it's merely performing a test on a potential spell, returning logical true or false".10565903
Thanks much! I was deliberately keeping the "proof" down to a lite version to keep the story flowing (I didn't even get into quining and other details), so it's reassuring to hear that it still reads well.
10565927
Good points. I did consider modelling G on Turing's approach to the the halting problem, along the lines of your description of f(x), but there were a couple issues. One was that it didn't really get across the self-referentiality which is the important, mind-bending part of Gödel's theorems. Also, I was doubtful that the validation and typing mechanisms of structured magic would even allow functions that "deliberately" include the possibility of an infinite loop. For example, if you define a function like:
f(x) = f(f(x))It shouldn't type-check at all, because the argument x isn't properly typeable (it requires, essentially an "infinite" or unbounded type).
So I went back to something closer to Gödel's theorem, banking on the assumption that the validation mechanisms of structured magic would permit
G(S,x) = ~ Derivable(S,x)since it's simply expressing a general operation on an unspecified spell-text, but would choke on
G(S,g)since it's a specific instance that's problematical because of the self-reference of "g" -- whatever answer the validation mechanisms determine for Derivable(S,g), the spell G(S,x) produces the opposite effect. This is inconsistent if G is derivable, but not if it isn't. And that's basically the crux of Gödel's theorem: you use self-reference to construct a theorem/program/spell which, owing to its self-reference, is asymmetrical: it's inconsistent within the system, but not outside of it -- and when it's outside, it's perfectly true/valid/castable.
Hoofwave, hoofwave, pay no attention to Trixie behind the curtain. But that's the main thing I was shooting for here, getting across the essentials without turning this into an actual logical treatise. Since it's supposed to be a metaphorical presentation of Starlight's "redemption" from her own self-imposed guilt. And also, in a way, about her being the one pony that doesn't fit in, doesn't work within the rules, who in fact proves the rules are incomplete by existing outside of them.
As a side note, after finishing this story, I happened to rewatch the "Tough Love" scene in "School Daze", in particular the bit where Starlight slaps the EEA rulebook into the water:
And I was like -- oh yeah. That's who Starlight is. And it seems like she even knows it herself now.
As a mere astrophysicist whose knowledge of programming largely encompasses "I want to do THIS with THAT and make it look pretty" and little else, much of the philosophical math-code-proof stuff is a bit beyond my comprehension. Even so, I really enjoyed this story, particularly the fleshed-out insights into Starlight's youth and development over time. And of course, I'm always a sucker for a good intellectual story like this, even if some of it goes over my head. Cheers, mate.
10565979
Thanks much, Eroraf86 -- that was my goal, to make Starlight's "presentation" at least solid enough to be interesting to folks who are familiar with issues like this, but also to make the rest of the story engaging enough on its own. It's great to hear it works for you!
Ohh ho ho ho this broke my little big brain, my brain needs to get bigger, and guess what?
You just gave me a reason to study magic and other junk.
Edit: I don't understand it well enough. Eh, I'll get there eventually.
Wow. The Grand Theory of Starlight Glimmer - and it all being wrapped around a way of seeing the world that's almost intuitive to her, but the average reader will struggle to comprehend, is so fitting.
I'm honesty a little proud of myself to recognize the Halting Problem in action, even though I had to look the up the darn name of the thing.
For those of you who aren't quite grasping the concepts that Starlight is explaining here, or just don't like math, here's a video that explains:
The Halting Problem, or... Proof Why Computers (Or in this case, Magic) Can't do Everything.
Should be Sunburst I think.
10566159
Thanks for catching that -- fixed!
Really enjoyed this story, though some of the actual science stuff went a little over my head there’s enough characters insight and study to make this an enjoyable read, even if the thesis itself is a little hard to understand for someone like me.
Also after all that, it makes it all the more fitting for Starlight to become the headmare of the friendship school.
Very nice work
Edit: okay reading through it properly again I kind of have a better understanding f what it’s talking about but still not 100%.
Thank you for a wonderful story I hope you will do a sequal I think for an encore Starlight should end up as an Alicorn and her title will be the princess of time. Just thought keep up the great work.
10565973
That makes sense, though requiring termination makes recursion a lot more complicated. It's not easy to build a system that can distinguish
f(n) = if n <= 1 then n else f(n - 1) + f(n - 2)fromf'(n) = if n <= 1 then n else f'(n + 1) + f'(n + 2). Coq/Lean manage this by requiring every recursive definition to come with a proof of termination.In most statically typed programming languages,
fis a perfectly type-safe (though not very useful) function, whose type isforall a. a -> a. Coq's termination checker will indeed reject this (the recursion is not well-founded), though the type checker otherwise has no problem with it.This makes for a rather unusual system, which doesn't correspond to anything I know of IRL. Usually once you define a function or predicate, the type system allows you to apply it to any argument of the correct type, whereas here it sounds like there's some additional restriction. It maybe makes more sense for
G(S,x)to be a proposition: you can have a proposition whose statement is well-typed but which is not provable. (By the way, I've been taking "derivable" to mean "type-safe" - hopefully that's correct.)But, as you say, hoofwave hoofwave - this is not really the point of the fic.
I won't pretend to have understood this, but it is well written and i liked it anyway.
So there, have your like and favourite :P *sulks*
Tbh the fact that people make Nightmare plushies for the purposes... undetermined, is such an amazing detail. The boring backwater of Ponyville didn't know who Nightmare Moon was, but apparently the world at large didn't really forget. Such a wonderful little detail. None of that 'Celestia made the world forget woooo' stupid... stuff people go for.
10566841
Thanks much! My own take on it is that while mention of the "lost Sister" Luna has been discouraged/repressed by the Court and the public, perhaps out of deference to Celestia's feelings (see The Night That Luna Returned), Nightmare Moon by a kind of perverse contrast has taken on a larger-than-life, near-mythical status as the Evil One of the pony world. Which obviously makes her return and redemption all the more apocalyptic and startling to the current generation of ponies.
This suggests that there might still be Nightmare-worshippers, as well as the more common use of the Nightmare as a symbolism of rebellion for young ponies: goth and other "dark" stylings, heavy-metal rock bands, and even toys for those who like their Elder Gods in cuddly form.
To be fair, the description of the room's contents is partly extrapolated from the one momentary on-screen glimpse we get of Starlight's old bedroom:
Whether this is intended to be an actual depiction of her room as she left it, or just a throwaway "the horror, the horror" joke, is an open question. But it was fun figuring out what all the various elements in it might represent in pony culture.
I knew just enough programming and math to sort of follow along. Fun stuff.
I very much liked this story, so please take these quibbles in the spirit of engagement and not as complaints.
Well no, there's a lot of true-but-unprovable statements. If the Godel statement were the only one, then no one would care about the incompleteness theorem in practice.
You got this right later in the lecture, it's just the introductory summary that's a bit sloppy.
If this spell behaves the way you say it does, then it's doing an infinite amount of work, i.e. ponies built a hypercomputer. Starlight handwaves that by mentioning clever ways to avoid an infinite loop, but that doesn't work here; whenever the answer is "no, x is not derivable from S" then this loop really does need to be infinite.
In the real world, we can define
Derivable(S, x)as a mathematical object. But we can't implement it, in the practical sense of asking what its return value is for any x.If ponies can... that has huge consequences, that go far beyond proving things.
Otoh, if
Derivablejust does a brute-force search up to some finite upper-bound on proof length, then it'll miss any proofs longer than that bound, and thus not always return the right answer. And even that limited version would still be solving an NP-complete problem, with all the consequences that brings.Starlight proved that you can't verify every spell. This is not the same as not being able to represent them. The "universal notation" part of Sunburst's project is still viable, even while the "automating the process of invention" part got shot down.
10567795
Thanks for reading! And the feedback is appreciated.
Starlight is being a bit loose and dramatic here, but note that she's using "one" in the sense of "at least one", not "exactly one". Because true, at the very least one can conjoin G with any number of other statements (G & X & Y & ...) and produce a series of trivially equivalent statements. But the essential point is that there is at least one such statement G. I needed to strike a balance throughout between logical exactitude and concision, just to keep things accessible.
Yep, I agree. I did want to have the scene at the end, though, where Starlight provides a practical demonstration of the spell, rather than simply ending with "Q.E.D." which would be kind of boring, so I did need to assume a pony-world method for performing such exhaustive checks (Clover's Countably Concurrent Conjuration in this case). But the nice thing about Equestria is that even this isn't much of a stretch, narratively speaking. After all, this is a world where characters can self-teleport, which is already potentially in conflict with quantum physics, and can also self-levitate, which is probably disallowed by thermodynamics. Plus pegasi can push clouds around, which is very cool but you just have to roll with it.
It's like that wonderful line from Equestria Girls:
Spike: "The talking dog is the weird thing about all of this?"
Fair enough -- how about if I change it to "represent and verify" to be more exact?
Thanks again!
Man this was fun to read. I wish I understood what they were talking about, but it was fun to read none the less.
(If someone could tell me why this is so incredible, I would be very happy.)
You studied math and its history to write a Starlight Glimmer story becoming better than before?
While how her attempt to build an Utopian society was not possible because, to put it simply, there are always odds ones out?
Much compliments. You made it blends into the story you wanted to tell and not being an textbook like some hard SF.
Ps
This is a nitpick, but using a word like “debugging” made me think of computers and techs instead a world of magic. How about simple “trial and error”?
10568041
Math and computability theory, since structured magic has similarities to both logic and software development.
Worse than that -- because no matter how hard she tried, Starlight herself would always be the odd one out, since she couldn't make it work without her magic. ("Don't you mean a G, Miss Glimmer?")
Thanks! That's what I was hoping for with this!
It's actually intentional that structured magic straddles the line between logic and software development. Spell creation is like writing programs, Starlight notes that spells have "bugs" and/or may not always halt, and Starlight's whole approach to magic reflects the programmer's perspective -- especially the feel of "rolling up" a spell and feeling like it's finally working rather than just sputtering. In this universe, Starlight ends up playing the roles both of Gödel the logician, and Turing the computability expert -- with maybe a bit of Ada Lovelace and Grace Hopper thrown in there for good measure. Quite a lot for one pony, but Starlight has always been "something of a natural"...
Starlight, "TWILIGHT!! I BROKE MAGIC!!!"
Twilight, "Just calm down. How can you tell you broke magic?"
Starlight points to Season 9.
Twilight, "Oh Tartarus... HOW DID YOU FUBAR EVERYTHING THIS BADLY, STARLIGHT SUE?!"
This story reminds me in a way of the halting problem in computer science
10568651
It's more directly inspired by the structure of Gödel's theorem, though Turing's answer to the halting problem was also inspired by Gödel's work.
I really enjoyed reading this story! I understood someway through that there were some elements of computer science, functions, pointers, and recursion. Honestly, this made me more intrigued becayse I was seeing the story relate to what I understand about all those points. Great story!
10568961
Thanks! The stock advice for writing is "write about what you know".
This is one of those rare cases where it actually works...
most of this went over my head, as I think a lot of these concepts fly a bit higher than that Intro to Python course I took in freshman year, but I think the fact that I was able to thoroughly enjoy this regardless is a testament to your writing. This was super cool, and a great read!
This was cute in so many ways, thank you for the read!
Definitely read it as 'Starlight invents magical computer science, and begins realizing the issues that arise when you have that much compute at your disposal and the limitation is no longer 'This is too much effort to math' but 'PARADOX!!!'
10567867
Self-levitation does not seem to me to obviously break thermodynamics. From an energy conservation point of view (since I'm not sure how you could meaningfully discuss the entropic effects of self-levitation), self-levitation is not obviously worse than, say, a droplet of oil floating in the air thanks to the coupling between its charge and an external electric field, or a maglev train hovering because of the magnetic interactions between itself and the track. Of course there could be various interesting qualities to the interaction, e.g. a variant of Earnshaw's theorem, but from a general point of view it does not clearly seem forbidden (if you treat magic as an addition to known physics as opposed to an external thing).
Anyway, as to the story itself I thought it was interesting--of course, I recognized where you were going pretty quickly, so it was more a matter of seeing how you got there than anything else. The main problem I had with it was that some of the dialogue seemed clunky and unnatural, especially in the early foal segments. It was a little jarring.
10569931
Self levitation could also be like hooking a magical pulley into the air, at which point if you had a rope from it you could 'self levitate'
Like the real question is 'How can you use magic to anchor an object in the air in such a way that pulling/pushing on it acts in a way that is not what you would expect given the normal rules of gravity & mass interaction (Eg, it stays floating when you pull on it and thus can be used as a floating 'stair' or something)
10569931
You're right, I was thinking of the wrong type of conservation: it's energy, not entropy that's the issue.
Self-levitation (that is, closed-system levitation, i.e. using an object's own energy of whatever form to "hover", as opposed to open-system, external-force levitation, like maglev or the droplet of oil example) is basically anti-gravity, that is, using energy to "flatten" space-time in your vicinity. There are arguments that this can violate conservation of energy, since you could use it to shape space-time to create a perpetual motion machine.
But speaking on a non-scientific, gut level (since barring a solid definition of quantum gravity this is all we have) it seems like an object should not be able to store sufficient energy to negate its own mass in this fashion. OTOH, in the pony world, pegasi can walk on clouds, so there's at least some kind of negation of normal mass and/or interaction going on here. Hence Starlight being able to "fly" by self-levitation isn't so much of a stretch in this world. (That, and she has such deep magic reserves that she can afford to "burn" magic to that extent, without worrying about suddenly running short.)