HNHacker News
TopNewBestAskShowJobs

i_k_k

225 karma · joined September 7, 2022

submissionscomments
i_k_k··on Topology, a Categorical Approach (2020)
I never understood this either...

Category theory works with collections, which can be modeled as sets -- or if you want to deal with categories of sets and other "large" categories -- as proper classes. And you can use a set theory that incorporates classes, like Morse-Kelley, to model this. IOW, it seems like category theory can be modeled in set theory.

On the other hand, I've not seen a rigorous set of axioms for category theory that didn't presuppose a notion of set or category or "collection".

Set theory also sheds a lot of light on what feel like foundational issues: sizes of sets, independence of axioms, etc.; I haven't seen something similar out of category theory.

Love for a category theory partisan to chime in with more here -- I'm definitely not an expert.

i_k_k··on A Geometrically Natural Uncomputable Function (2008)
My favorite "natural" undecidable function is the the Post correspondence problem (https://en.wikipedia.org/wiki/Post_correspondence_problem).

In short, imagine I give you a set of dominoes that have strings on the top and the bottom. E.g.:

D = { banan/b , 0/an, a/a } (Where 0 is the empty string.)

A solution is a sequence of dominoes selected from D with replacement such that the string made up of the tops and the bottoms are the same. In the case of D, the sequence:

[banan/b , 0/an, 0/an, a/a]

is a solution. Solvable(X) = 1 if there exists a non-trivial solution for X and = 0 if not. So Solvable(D) = 1.

Solvable(X) is undecidable. Like a lot of these kinds of problems, the proof is gross, but the basic intuition is that I can encode the compute history of a Turing machine in a set of dominoes so that there is a solution iff the machine halts.

i_k_k··on Penetration testing wireless keyboards
I remember thinking that XOR with a password was awesome encryption. Then again, this was back in the BBS days, 3DES was the tits, and I was thirteen.
← PreviousPage 2 of 2