Gehinnn

A nice property of monoids is associativity, which allows for some interesting incremental algorithms, e.g. by using balanced trees: If the fold of × on a list is computed in clever way, the fold of × on a list where one element is modified can be computed in logarithmic time, given the computation of the first list.

A good example for a monoid are strings with the string concatenation operation! This is used a lot in text editors. Homomorphisms are also of practical relevance here.

If × is a commutative group operation (i.e. inverse elements exist and a×b=b×a), that can even be done in constant time in a trivial way.

A good abstraction shouldn't make its usage shorter, it should make the proof that the usage is correct shorter.

This usually means the total amount of assumptions needed to prove everything correct is decreased. (when the code is not actually formally verified, think of "proof length" as mental capacity needed to check that some unit of code behaves as intended)

> I think the primary change is that these debates were focused on producing diffs that humans read; now the debate is whether the algorithms can accomplish this result with no human involvement at all.

The better the diff captures the intent of the user change, the easier the diff is to read, AND it also becomes easier to understand merge conflicts, as the conflict becomes a conflict of intents and not characters. Sometimes certain conflicts can even be avoided if the diffs are chosen right (or are expressive enough, e.g. when code moves can be detected).

I'd pay a lot per month if I wouldn't have to care which subscriptions I need and could just access everything.

I wouldn't pay a lot for any particular service that I'd just use only once or twice per month. I only ever read "the verge" if it is linked from HN or somewhere else. A subscription just doesn't make sense for me.

I was referring to the press release article. I also looked at the paper now, and to me their presented proof looked more like a technicality than a new insight.

If it's not solvable in polynomial time, how did nature solve it in a couple of million years?

I skimmed through the paper and couldn't make much sense of it. In particular, I don't understand how their results don't imply that human-level intelligence can't exist.

After all, earth could be understood as solar powered super computer, that took a couple of million years to produce humanity.

Basically the linked article argues like this:

> That’s because cognition, or the ability to observe, learn and gain new insight, is incredibly hard to replicate through AI on the scale that it occurs in the human brain.

(no other more substantial arguments were given)

I'm also very skeptical on seeing AGI soon, but LLMs do solve problems that people thought were extremely difficult to solve ten years ago.

Love this for searching in movie subtitles!

I think it's quite often possible! Most of code acts as implication. Given this piece of data (of this shape), I can compute that. Or given I'm a valid object (constructor completed successfully), I can do this and that.

However, very often, unstated assumptions sneak in.

For example, assuming to understand how to interpret a certain string, which usually causes all kind of escaping issues.

I think DRY should be more "Don't repeat assumptions".

Or rather, don't assume the same thing in two different places, especially not implicitly.

Avoiding code duplication mostly follows from that.

I thought this was about doing UI in rust, but it's just Javascript/react.

Also, in the demo screenshot, the margins of the agent/you labels feel off.

Here's how we implemented the Myers diff algorithm in VS Code: https://www.youtube.com/live/yWy-0TNVsLg

On top of the core algorithm, we have many heuristics to show much nicer differs in many cases.

Reading this article, I want the same now for js code that involves web-workers...

How can I write code that involves a webworker in a way that I can simulate every possible CPU scheduling between the main thread in the webworker (given they communicate via post message and no shared array buffer)? Is it possible to write such brute force test in pure JS, without having to simulate the entire computer?

Would it be far fetched to say object oriented programming is inspired by nature/physics?

And thus, "more natural" than, let's say, procedural programming.

Animals can be modeled nicely with objects/classes. Physical objects do have internal private state and public interfaces. Also in nature, usually, you have multiple similar objects that work the same but have different internal state.

I'm pretty sure that you have either an undecidable problem or a non deterministic piece of code that sometimes computes some value, other times a different value, depending on how the threads are scheduled. Neither is good.

The most underrated insight about logarithms is that for almost all practical applications, log2(n) is smaller than 32.

The difference between a O(1) and O(log n) algorithm is usually not that big!

I think there are different ceilings. And probably everyone has some spaces where they didn't reach their ceiling yet.

Personally I'm all against cars, but I don't see why these unexpected costs don't apply to public transport as well.

The noise of trains also reduces the value of the properties next to the tracks.

Doesn't the free market regulate this?

I can also recommend https://www.worldtimebuddy.com/

It's surprising how much ads all these tools show though.

With dependency order you mean dependants before dependencies? (and dependencies lazily when they are requested again by the dependant)

If you update dependencies before dependants, the dependant might not depend on all it's dependencies anymore (because a derived might depend on A only if the observable B is true) and you do too much work/run into glitches.

I implemented the eager recomputation model for the observable utilities in vscode [1] and it quickly fell on my feet because of these glitches.

In particular this is problematic if you have observable optional state that has inner observable/derived state and someone reactively reads the outer state and then it's inner if the outer one is defined.

Then you clear and dispose the outer state and at the same time set some other observable value that the inner derived depends on. With eager recomputation, it can now happen that the inner derived is recomputed, even though the inner state is disposed.

[1] https://github.com/microsoft/vscode/blob/fe9154e791eafb4f18d...

When processing "pi = 3", I'd rather have the error "cannot assign to constant" than "unexpected token =".

Generally, whenever I write a parser+checker, I try to have a very relaxing parser and then all the checks in the checker.

A tag system is actually a deterministic computational model

https://en.m.wikipedia.org/wiki/Tag_system

That's not how you show lower bounds.

The problem is function f that gets a list of words D and a word w of length n and returns a list of indices I where to split w such that each part is in D or "false".

Cleary, I has length at most n and the indices in it are also at most n. Also, you need to look at every word in D. Thus, the trivial lower bound of the complexity for an algorithm that computes f is O(n+|D|).

To prove a tighter lower bound, you would need to show that every algorithm that does it in in linear time has a bug - you need to find this "pathological" case for every imaginable algorithm!

Afaik it is still unknown of SAT has a quadratic lower bound! https://cstheory.stackexchange.com/questions/17789/is-there-...

I'd bet the last problem (if you can prove that N^2 is a lower bound for the last problem) is open or at least very hard. Showing lower bounds without oracles (where you can prove that the oracle has to be called a certain number of times) is not an easy endeavor.

Cannot you get extremely unlucky so that for one input all the PRNG seeds map into a subset of the 1/3 unhelpful random strings?

I'd say its less about writing defensively (protecting yourself against libraries who don't deliver what they promised) and more about users making stronger assumptions than what the library promised (eg assuming json string literals contain no escaped characters so that a simple ". *?" to match the value is fine, that some value is always defined or generally that a behavior observed two out of two times must be the rule).

Can you recommend an accessible proof for this? (is this simply because if the error probability is too low, it must be zero?)

Are there problems in BPP that can defend against "helping" PRNGs by diagonalizing against them somehow?

You can also mix problems to change the average complexity.

Take SAT (in NPC) and encode each instance with a word over a binary alphabet (eg. A and B). Then add 2SAT (in POLY) and encode it using an alphabet with four letters (eg. A, B, C and D). If a word has only As and Bs, treat it as SAT, otherwise as 2SAT.

If you chose a random instance of length n (= a sequence of n letters from A to D), the probability it is from SAT (ie contains no C or D) is less than 1/2^n.

Thus most instances are solvable in poly time, and only with neglectable probability you get a "harder" problem from SAT.

Still, this problem is NP complete, as it is in NP and you can trivially reduce SAT to it.