-
Network influencers
Think about your social network: the people you know, the people that each of those people know and so on. Each of them is influencing everybody else, directly or indirectly, to different extents. Someone starts using a new slang and, soon, a lot of people are following the trend. Or someone is infected with a virus, which may rapidly spread among the people that had contact with the infected person. Conversely, other people may not spread fads or viruses so much.
-
How many paths must a man walk down?
Every morning, John walks to the nice little coffee shop not far from his house. He just can’t get enough of that chai latte with an extra shot and cinnamon on top. One day, immersed in his musings about the nature of reality, he wondered, between a sip and another: “If I made a different path from home every day, how long until I would have to repeat a path?” It didn’t take too long until he realized that the answer is “infintely many” (you can always walk in circles and so on). Being a reasonable man, though, John also wants to keep his journey relatively short. No more than four blocks. Sometimes five, if the weather is nice.
-
Does this function accept itself?
In the previous post, I started by posing a question: is it possible to implement some algorithm that can tell whether a function accepts a regular expression? And the conclusion was that, if it were possible, there is another thing that would also be possible: to tell whether any given function accepts any given string. This is what we called a “universal decider”. I ended by mentioning that the universal decider was impossible to build (and therefore the regular expression decider). In this post I’ll show why.
-
Functions and Regular Expressions
Regular expressions are one of those things that bring joy and frustration at the same time to most software developers. At one point or another, we’ve all written functions to match strings against some regular expression, as part of a bigger function, class, component etc. In this post, I want to show you one of the counterintuitive results from Computability Theory, that involves regular expressions. The code samples are all in Scala, mainly because, in my opinion, it is concise in many respects, but, at the same time, reasonably familiar to a wide audience of developers.
subscribe via RSS