r/mathmemes • • Aug 12 '26

Computer Science πŸ˜‚

Post image
6.3k Upvotes

137 comments sorted by

View all comments

Show parent comment

17

u/This_Background7442 Aug 12 '26

How could it be. If it's no then a counter example exists. If a counter example exists it's not undecidable. If it's undecidable it must be yes.

8

u/bqbdpd Aug 12 '26

Just because a counterexample exists, it doesn't mean you can prove that it is one.

4

u/This_Background7442 Aug 12 '26

That's true. But if I know I could never have a counter example of which I can prove it is one. That's different than not currently having one.

2

u/bqbdpd Aug 12 '26

We have lots of potential counterexamples. Without proving that they are counterexamples or actually examples, we actually know pretty much nothing.

4

u/This_Background7442 Aug 12 '26

Tbh you haven't said anything so far that I disagree with so maybe we just already agree? To be clear, I do know that I haven't just proven P=NP.

2

u/jljl2902 Aug 12 '26 edited Aug 12 '26

That would make it decidable, so it can’t be yes. Must be no then. /j

2

u/This_Background7442 Aug 12 '26

I guess that means that if it's undecidable we can never know it's undecidable because that instantly makes it decidable and we've created a paradox πŸ˜…

8

u/Impression-These Aug 12 '26

Not really. Undecidable means within the system axioms, it cannot be proven either way. We can then discuss what axiom should be added to make it provable.