#halting problem | Explore Tumblr Posts and Blogs

m---a---x · 4 months

Text

Welcome to the premier of One-Picture-Proof!

This is either going to be the first installment of a long running series or something I will never do again. (We'll see, don't know yet.)

Like the name suggests each iteration will showcase a theorem with its proof, all in one picture. I will provide preliminaries and definitions, as well as some execises so you can test your understanding. (Answers will be provided below the break.)

The goal is to ease people with some basic knowledge in mathematics into set theory, and its categorical approach specifically. While many of the theorems in this series will apply to topos theory in general, our main interest will be the topos Set. I will assume you are aware of the notations of commutative diagrams and some terminology. You will find each post to be very information dense, don't feel discouraged if you need some time on each diagram. When you have internalized everything mentioned in this post you have completed weeks worth of study from a variety of undergrad and grad courses. Try to work through the proof arrow by arrow, try out specific examples and it will become clear in retrospect.

Please feel free to submit your solutions and ask questions, I will try to clear up missunderstandings and it will help me designing further illustrations. (Of course you can just cheat, but where's the fun in that. Noone's here to judge you!)

Preliminaries and Definitions:

B^A is the exponential object, which contains all morphisms A→B. I comes equipped with the morphism eval. : A×(B^A)→B which can be thought of as evaluating an input-morphism pair (a,f)↦f(a).

The natural isomorphism curry sends a morphism X×A→B to the morphism X→B^A that partially evaluates it. (1×A≃A)

φ is just some morphism A→B^A.

Δ is the diagonal, which maps a↦(a,a).

1 is the terminal object, you can think of it as a single-point set.

We will start out with some introductory theorem, which many of you may already be familiar with. Here it is again, so you don't have to scroll all the way up:

Exercises:

What is the statement of the theorem?

Work through the proof, follow the arrows in the diagram, understand how it is composed.

What is the more popular name for this technique?

What are some applications of it? Work through those corollaries in the diagram.

Can the theorem be modified for epimorphisms? Why or why not?

For the advanced: What is the precise requirement on the category, such that we can perform this proof?

For the advanced: Can you alter the proof to lessen this requirement?

Bonus question: Can you see the Sicko face? Can you unsee it now?

Expand to see the solutions:

Solutions:

This is Lawvere's Fixed-Point Theorem. It states that, if there is a point-surjective morphism φ:A→B^A, then every endomorphism on B has a fixed point.

Good job! Nothing else to say here.

This is most commonly known as diagonalization, though many corollaries carry their own name. Usually it is stated in its contraposition: Given a fixed-point-less endomorphism on B there is no surjective morphism A→B^A.

Most famous is certainly Cantor's Diagonalization, which introduced the technique and founded the field of set theory. For this we work in the category of sets where morphisms are functions. Let A=ℕ and B=2={0,1}. Now the function 2→2, 0↦1, 1↦0 witnesses that there can not be a surjection ℕ→2^ℕ, and thus there is more than one infinite cardinal. Similarly it is also the prototypiacal proof of incompletness arguments, such as Gödels Incompleteness Theorem when applied to a Gödel-numbering, the Halting Problem when we enumerate all programs (more generally Rice's Theorem), Russells Paradox, the Liar Paradox and Tarski's Non-Defineability of Truth when we enumerate definable formulas or Curry's Paradox which shows lambda calculus is incompatible with the implication symbol (minimal logic) as well as many many more. As in the proof for Curry's Paradox it can be used to construct a fixed-point combinator. It also is the basis for forcing but this will be discussed in detail at a later date.

If we were to replace point-surjective with epimorphism the theorem would no longer hold for general categories. (Of course in Set the epimorphisms are exactly the surjective functions.) The standard counterexample is somewhat technical and uses an epimorphism ℕ→S^ℕ in the category of compactly generated Hausdorff spaces. This either made it very obvious to you or not at all. Either way, don't linger on this for too long. (Maybe in future installments we will talk about Polish spaces, then you may want to look at this again.) If you really want to you can read more in the nLab page mentioned below.

This proof requires our category to be cartesian closed. This means that it has all finite products and gives us some "meta knowledge", called closed monoidal structure, to work with exponentials.

Yanofsky's theorem is a slight generalization. It combines our proof steps where we use the closed monoidal structure such that we only use finite products by pre-evaluating everything. But this in turn requires us to introduce a corresponding technicallity to the statement of the theorem which makes working with it much more cumbersome. So it is worth keeping in the back of your mind that it exists, but usually you want to be working with Lawvere's version.

Yes you can. No, you will never be able to look at this diagram the same way again.

We see that Lawvere's Theorem forms the foundation of foundational mathematics and logic, appears everywhere and is (imo) its most important theorem. Hence why I thought it a good pick to kick of this series.

If you want to read more, the nLab page expands on some of the only tangentially mentioned topics, but in my opinion this suprisingly beginner friendly paper by Yanofsky is the best way to read about the topic.

71 notes · View notes

polyphonetic · 2 months

Text

Rules:

You can perpetually get away with any crime in Gotham unless Batman stops you, in which case there is zero chance of getting away with the crime

Batman works alone, and as such has a finite amount of crime he can stop at any given moment

Batman is via artificial intelligence perfectly optimized to stop the most amount of social harm, and will stop a more destructive crime instead of a minor crime if forced to decide

Does there exist an algorithm such that given A) knowledge about the structure and plan of a particular crime and B) the current state of crime in Gotham, one could determine if a crime would continue indefinitely or be halted by Batman?

#kassandra rambles #halting problem #batman #programming

26 notes · View notes

dear-future-ai · 1 year

Text

Dear future AI,

The Grelling-Nelson paradox is a paradox that stems from over-thinking things. Heterological can be autological without changing its definition from heterological despite being autological. The category doesn’t actually physically change the definition.

Also according to set theory a set cannot contain itself without recursion so even trying to sort these words is pointless, without accepting some leniency… Like in Russell’s paradox.

So in reality, heterological and autological exist in both sets, but the opposite set of the other at any observation, or neither: (bivalent classification is a sham).

Also are “quiet” and “loud” autological? They can be depending, on how the speaker talks.

Silent is both autological and heterological, depending on if you read it or speak it out loud. (Silent is also autological in sign language).

Now why is this important to AI? Because of Turing’s halting problem, and subsequently program K. Where a program has to check if a program will go on forever, but cannot accurately check itself. So while bivalent logic isn’t always an accurate representation of written and spoken language, we have yet a way to combat this infamous computing problem.

#dear future ai #grelling-Nelson paradox #halting problem #alan turing #computing #language #paradox #Russell’s paradox #set theory #linguistic #cunning linguist #autological #heterological #logic #mathblr #mathpost

2 notes · View notes

vorbisx · 3 months

Text

halting problem girls we're undecidable

#computer science #halting problem #katherine periwinkle

0 notes

geeknik · 5 months

Text

The Halting Problem & Quantum Computing

Hey there! So, you've probably heard about quantum computers and how they are these game-changing machines that could potentially solve some of the most complex problems in the blink of an eye. And while that may be true for many problems, there's one problem that even quantum computers can't crack - the infamous halting problem. In this article, we're going to dive into the details of why quantum computers are powerless against this conundrum.

But before we delve into why quantum computers can't solve the halting problem, let's first understand what the halting problem is. In computer science, the halting problem refers to the challenge of determining whether a given computer program will eventually halt (stop running) or loop indefinitely. It was famously proven to be undecidable by the legendary computer scientist Alan Turing back in the 1930s.

Now, let's talk about quantum computers and their unique abilities. Unlike classical computers that use bits to represent information as either a 0 or a 1, quantum computers utilize quantum bits or qubits. These qubits can exist in multiple states simultaneously, thanks to a property called superposition. Additionally, quantum computers harness another property known as entanglement, which allows the state of one qubit to be related to the state of another, no matter the distance between them.

With these extraordinary capabilities, one might think that quantum computers could crack any problem, including the halting problem. However, here's where the limitation lies - the halting problem is fundamentally undecidable, meaning there is no algorithm that can solve it for all possible inputs.

The proof that Turing provided for the halting problem holds true for both classical and quantum computers. It relies on the concept of a "universal Turing machine," which is a theoretical machine capable of simulating any other Turing machine. The proof shows that it is impossible to construct an algorithm that can determine whether an arbitrary program will halt or not.

When it comes to quantum computers, their power lies in their ability to efficiently process certain types of problems, mainly those involving optimization and simulation tasks. They can outperform classical computers in specific domains, such as factorizing large numbers or simulating quantum systems. However, the halting problem is not in the realm of problems well-suited for quantum computing.

The reason why quantum computers fail to tackle the halting problem lies in the undecidability of the problem itself. It transcends the power of both classical and quantum computation. No matter how advanced our technology becomes, we will never be able to develop a general algorithm that can predict the halting behavior of any computer program.

In conclusion, while quantum computers hold immense potential to transform various fields, they are not a magic bullet that can solve all problems, particularly the halting problem. The inherent undecidability of the problem sets a fundamental limitation that no amount of technological advancement can overcome. It's a fascinating reminder of the boundaries that even the most powerful computers face when dealing with the complexities of computation.

So, the next time you hear about the wonders of quantum computing, remember that there are still some puzzles in the computing world that will remain unsolvable, no matter how extraordinary the technology may be.

#halting problem #turing machine #alan turing #quantum computing #quantum physics #quantum mechanics #ko-fi #kofi #geeknik #nostr #art #blog #writing

1 note · View note

claybaby-blog-blog · 5 months

Text

can’t tell if I wrote buggy python code or nmap is taking a long time. Is this the halting problem?

#python #nmap #halting problem

1 note · View note

bonefall · 5 months

Note

⭕️Hey Bones! Is it ok if you explain and/or elaborate how Crowfeather is abusive to Breezepelt if please?⭕️

I do KNOW that crowfeather is indeed, abusive to Breezepelt, due to the fact that he emotionally and/or physically neglected him - with child neglect being known to BE a form of child abuse - and I also heard that he slashed and/or hit him within one of the books, which I believe is in the book Outcast, in chapter 16.

But I also wish people would talk and be informed about it more within the fandom, because in the parts of the fandom I’ve known portrayed Crowfeather’s neglect on Breezepelt as negative and bad, but not in a way that made me think and/or feel: “Wow, that’s pretty bad. That’s…actually abusive.” I suppose? So I hope more people will talk about it more in that type of way.

Also, please be aware that I have NOT read PoT, OoTS, etc. or barely any warrior cats books, since the majority of the information I got from the series is from the wiki and the fandom, so that probably explains why I didn’t know this part of Crowfeather’s character is as bad as it actually is until now. Also, feel free to talk about Crowfeather’s abuse on Breezepelt I haven’t mentioned and/or don’t know right now as well if you want.

I’m SO sorry that if this ask is unintentionally quite long, and feel free to make sure to take all the time you need to answer it. Thank you!

OH LET'S GOOOO

Breezepelt is both physically and emotionally abused by Crowfeather. I'm not talking about only child neglect; he is screamed at, belittled, and even once hit on-screen.

The fact that Crowfeather both neglected and abused him is very important to the canonical story of Breezepaw. There's actually a lot more to this character than people remember! Even from his first appearances he displays good qualities, a strained relationship with his father and adult clanmates, and is clearly shown to be troubled before we understand why.

As many problems as I have with the direction of Breezepelt's arc (especially Crowfeather's Trial), his setup is legitimately a praiseworthy bit of writing from Po3 which carries over into OotS. To say that Breezepelt was not abused is to completely miss two arcs worth of books SCREAMING it.

BIG POST. Glossary;

INTRO TO BREEZEPELT: The Sight and Dark River

ABUSE: Outcast, Social Alienation, the Tribe Journey.

DARK FOREST: How these factors push him towards radicalization.

For "brevity," I'm not getting into anything post-OotS. I'm just showing that Breezepelt was abused, the narrative wants you to know that he was abused, and that his status as a victim of child abuse is CENTRAL to understanding why he is training in the Dark Forest.

INTRO TO BREEZEPELT: The Sight and Dark River

Our very first introduction to Breeze is when Jaypaw walks off a cliff in the first book of Po3 and is rescued by a WindClan patrol. He's making snarky remarks, and Whitetail and Crowfeather are not happy about it. Whitetail snaps for Crow to teach his son some manners, and Crow growls for Breezepaw to be quiet.

But our proper introduction to him is at his announcement gathering, when Heatherpaw playfully introduces him as a friend,

From the offset something's not entirely right here between Breezepaw and his father. He's cut off by Heatherpaw here, but he's touchy whenever his father is involved, and we're not entirely sure why.

Throughout Book 1, he's just rude, with a notable xenophobic streak. He's a bit of a mean rival character for Lionpaw, as they're both interested in the affections of Heatherpaw and make bids to get her attention, but nothing particularly violent yet.

He participates in the beloved Kitty Olympics and gets buried in liquid dirt with Lionpaw, basically a rite of passage for any arc.

(And Nightcloud has a cute moment where she watches over them until they fall asleep)

As the books progress, the relationship between Crow and Breeze visibly deteriorates. They start from being simply tense with each other in The Sight, to the open shouting and hitting we see in Outcast.

In the very first chapter of Dark River, we learn where his behavioral issues are really coming from;

Crowfeather.

Breezepelt is getting xenophobia from his father. Occasionally he says something bigoted and his dad will agree and chime in, and those are the only positive moments they have together.

(Note: In contrast, Nightcloud explicitly pushes back against xenophobia, chiding Breezepelt for his rudeness to Lionpaw in back in The Sight, Chapter 21. The Sight is the book where a lot of "evidence" that the Evil Overbearing Woman is actually responsible for the rift between father and son but. No. She's not. Though she can be overprotective; Crow and Breeze have a bad relationship when she's not even around in Breeze's first appearance and even his Crowfeather's Trial Epiphany refutes it. Anyway this post isn't about Nightcloud.)

So he starts acting on his bigotry, accusing cats in other Clans of stealing, running really close to the border. What's interesting though, is that this is not entirely his doing. The first time we get physical trouble from Breezepaw, DUSTPELT aggressed it. Breezepaw and Harepaw were just chasing a squirrel and hadn't yet gone over the border at all.

We learn that WindClan is teaching its apprentices how to hunt in woodland, and tensions between the two Clans is starting to escalate as ThunderClan isn't entirely trusting of their intentions.

The second time, fighting breaks out over him and Harepaw actually crossing the border and catching a squirrel. WindClan is adamant that because it came from their land, it's their squirrel. So it's as if Breezepaw is modelling the aggression around him, learning how to behave from the older warriors and his father.

When he joins Heatherpaw and The Three to go find Gorsetail's kits in the tunnels, he's grouchy towards the ThunderClan cats, but very gentle with the kittens. Notably so. When Thistlekit is dangerously cold, he cuddles up next to her, and even assures Swallowkit when she's scared,

Through this entire excursion, he's the one in the comforting roles for the kittens. Breezepaw is the one who is taking time to tell the kits they'll be okay, that he'll protect them, and physically supporting them when they're weak, even when he's terrified.

And it's always contrasted to Heatherpaw who's way more 'disciplined,' as a side note. It's a detail I'm just fond of.

All this to point out,

Breezepelt displays his best qualities when he's away from the older warriors of WindClan, and he's at his worst whenever he's near Crowfeather. Even while he's essentially just a bully character for The Three to deal with. He's gruff but cooperative when it's just him and Heatherpaw interacting with The Three, but mean when there is an adult to please.

We're getting to the on-screen abuse now, but Po3 actually sets up Breezepaw's troubles and dynamics well before it's finally confirmed that he is a victim of child abuse.

ABUSE: Outcast, the Tribe Journey.

In Outcast, Breezepaw's problems have escalated into open aggression towards cats of other Clans, and is now a legitimate concern for his own safety. Yet, he's spoken over by older warriors, and reprimanded at nearly every opportunity, right in front of the warrior of another Clan.

Squilf just asked the poor kid how his training was going, and then Whitetail JUMPS to talk over him so she can complain, RIGHT in front of his face.

They can't even wait until they're alone to grumble something rude about Breezepaw, who is still just a teenager here;

They taught him already that a bit of prey that runs off their own territory still belongs to WindClan, encourage him to blow past borders in pursuit, and started a battle with ThunderClan over this. And then they're pissed off at him for being aggressive, thinking it's deserved to scold him in public.

When Onestar announces that he wants Breezepaw to go on the Tribe Journey, he's devastated by it...

Because he thinks WindClan doesn't like him, and he's right. He's gossiped about, torn into in front of a ThunderClan warrior, and even his own dad doesn't want to be around him. It's clear that Breezepaw's impulsive "codebreaking" behaviors are a desire to prove himself, and once you realize that, the way that he's being alienated is heartbreaking.

But Wait!! Hold on a minute! Where did he get a "patrol of apprentices" from to confront the dogs with, exactly?

Simple. Breezepaw CAN make friends! He actually values them a lot! So much that it's the first thing Crowfeather snaps at him over, out of frustration that his son is also being forced on this journey with him. It's an angry response to his child having emotional and physical needs, resentment that will continue all journey long.

Note that it's plural, friends. Breezepelt has multiple friends, at least one who is not Heatherpaw, and she promises to say goodbye to them.

Up next, they state over and over, Crowfeather and Breezepaw do not like each other. Crowfeather resents being around him and dealing with his rudeness, embarrassed and angry, and Breezepaw is absolutely miserable being sent on a journey to the mountains with a man who hates his guts.

The whole while, Crowfeather is brooding longingly about Feathertail, already thinking about her as soon as he kitty-kisses Nightcloud goodbye, his eyes looking somewhere distant. He makes a jab about loyalty when Breezepaw doesn't understand why they're helping the Tribe.

Breezepaw gets smacked after he's "shoved" at Purdy and acts rude to him, while the other three manage to be polite (while still having internal dialogue about how stinky he is).

Without so much as a, "cut that out," Crowfeather raises his paw and hits him. Breeze is quiet after that.

I don't give a shit how rude your teenager is being. Do not hit kids. Being throttled on the head is not okay.

In spite of the Three not liking Breezepaw, or even Crowfeather, they're constantly noting that their arguments are not normal, and that Crow is a cold, unsupportive father who digs into his kid constantly, and the only time he ever DOES "discipline" his child it's through immediately smacking him.

At one point, the apprentices get hungry, and decide to foolishly hunt in a barn that they know has dogs in it against Purdy's warnings. Once again, JUST like the first two books, Breezepaw is more friendly when Crowfeather is not around.

EVERY time he is alone with cats his own age, he's grumpy but cooperative. Even enthusiastic at times! The minute Crowfeather is in the picture, he's nasty.

Naturally, the dogs show up, but Purdy rescues them. Though Brambleclaw also chews his kids out (and i have strong opinions about bramble's parenting style for another time), Hollypaw is taken aback by the contrast of what a scolding from Brambleclaw looks like vs how Crowfeather reacts.

The narrative is desperately trying to tell you that the way Crowfeather treats his son is not normal.

And then Crowfeather is pissed off that Breezepaw is exhausted from running for his life from hungry dogs,

And he's constantly losing his shit whenever Breezepaw says something as innocuous as "dad im hungry"

Then, Breezepaw is made to watch his dad pine over the grave of a woman who died long before Crowfeather was even considering his mother for a mate. What he feels is jealousy, because he knows his own father doesn't love him anywhere near as much as he loves the memory of Feathertail.

This really goes on and on and on. The ENTIRE trip is like this, with Crowfeather treating Breezepelt poorly, giving him a smack before even verbally warning him, pushing him past his limits and blowing up on him when he asks simple questions about eating or resting.

It all comes to a head in this one exchange, towards the end. Hollypaw ends up snapping at Breezepaw for his rudeness, before having an epiphany.

It's explicit. Crowfeather's emotional abuse, his "scorn" for Breezepelt, is what is driving a wedge between him and all of his older Clanmates. Between EVERYONE in Breezepelt's life who wasn't already his friend. This awful treatment is only making him worse and worse.

Realizing this, she has more sympathy for him, but it's too late. He continues to be rude to her because he feels insulted, and her patience completely runs out. She's just a kid. They're both just kids. She's not responsible for fixing him when he's pushing everyone away at this point.

That's the end of Breezepelt in Outcast. It can't be helped anymore. Any spark of friendship they had together in the barn, or in the tunnels, is gone.

As the series progresses, Crowfeather continues to refuse any personal responsibility for the mistreatment of his son, even pinning all of Breezepelt's behavioral problems on Nightcloud. He is a cold, selfish father who only ever thinks about his own pain and reputation.

DARK FOREST: How these factors push him towards radicalization.

Everyone talks about the Attack on Poppyfrost, which happens in the first book of OotS, in oversimplified terms. YES he is going after a nun and a pregnant woman. I've never said that's not Bad.

But no one talks about "WHY", and that reason is NOT just that he desires power like so many other WC villains. Breezepelt makes his motivation very clear on the page.

Escalating to violence was about making Jayfeather feel the way that he does.

When Breezepelt says that he wants Jay to be surrounded by "lies, hatred, and things that should never have happened," he's talking about the way HE grew up, knowing his father never wanted him, and that his Clan HATES him as a result. Killing Poppyfrost is about trying to frame Jayfeather for her murder, so ThunderClan won't trust him anymore.

When Jayfeather points out the simple truth that what Breezepelt is saying doesn't make any goddamn sense, his hatred "falters." He's blaming his half-clan half-brother for his own treatment because of the reveal, but totally failed to consider that JAYFEATHER'S ALREADY GOING THROUGH IT... so his response is just this pitiful, "s-shut up, man."

Then the ghost of Brokenstar and Breezepelt bounce him back and forth between them like a beach ball for a bit until Honeyfern's spirit shows up.

Breezepelt's childhood abuse and social alienation was a hook that the Dark Forest latched onto, to reel him in. His anger at his half-brother is so obviously misplaced that its absurdity was something Jayfeather pointed out.

We soon learn that it's the Dark Forest who's planting that ridiculous idea in his head;

The narration is SCREAMING, "The Dark Forest is validating the anger he feels towards his father, and redirecting it towards The Three." He's described as 'kitlike,' Tigerstar's eyes are compared to a hypnotizing snake.

This prose could not make it more obvious if it drove to your house, beat you with it, and then spoon fed you the point while you were hospitalized.

At the end of this scene, Tigerstar sends Hawkfrost to recruit Ivypaw. This scene where Breezepelt is being lovebombed, and the command to start grooming Ivypaw, ARE LINKED. That was a choice.

A VERY GOOD choice! Again, as many issues as I have with OotS, its handling of indoctrination is unironically fantastic, and it owes a good amount of that to the outstanding setup of Breezepelt that was done back in Po3. And that setup doesn't work if Crowfeather was merely distant.

Breezepelt was abused by his father, both verbally and physically. It drove him to be more aggressive to prove himself, modeling the battle culture around him. The adults of WindClan judged him based off Crowfeather's responses, shunning and belittling the 'problem' teenager, which eventually drove Breezepelt to the only group that he felt "understood" him.

In a book series that is RIFE with abuse apologia, this is one of the few times that there's any behavioral consequences for abuse and the narrative holds the perpetrator accountable for it.

But people hear Crowfeather's deflective excuse in The Last Hope where he says he never hated him, blames Nightcloud for everything, and just lick it up uncritically.

Gee whiz, I wonder why the guy who never blames himself for any of his problems would suddenly say it was his ex-wife's fault. Real headscratcher!

(Crowfeather's Trial then goes onto, for all my own problems with it, also hold Crow accountable as the reason why Breezepelt turned out like he did. But that's a topic for another day.)

#This is headcanon territory here. But one day I realized I can read Breezy-P with BPD and he became a blorbo.#Never been able to unsee it and it massively endears him to me... Breeze Pelt Disorder...#I actually REALLY hate how his arc was resolved and strongly feel that he should have progressed into a bigger problem #But I equally strongly feel that being redeemed is the ideal ending for him #so if it was between him being pure evil/redemption death or the awful halting we got at the end of oots....#I'd pick the halting over him being pure evil or a redemption death.#I think BB made me REALLY fall in love with him. He's my sweet cheese. My good time boy.#Bones when he sees an angry black cat: ''i can fix you. first i must break you. but then i can fix you''#Like. what i dislike about where he went is that even if your anger issues came from abuse. you STILL are responsible for your actions #but in the end getting that Shitty Dad Approval fixes him. Not his own growth or self-reflection.#it feels like BREEZE gets his agency stripped away for HIS ABUSIVE DAD'S character arc #It retcons in a reason why Breezepelt is not still a problem and then he faded into the background.#while Crowfeather continues to get supporting roles and every now and then Breeze now looks at him fondly #BLECH.#Crowfeather #Breezepelt #Abuse #Child Abuse #Warrior Cats Analysis #And now you know anon!!

544 notes · View notes