The 3 way merge editor actually shows the branch name!
1,104 karma · joined June 2, 2017
Still, this problem is NP complete, as it is in NP and you can trivially reduce SAT to it.
This is true. The condition is false (halt cannot be implemented by using length), thus the implication is true, regardless of the implicant.
In general: Let P be a statement. Lets assume that the Turing Machine T solves the halting problem - let's call this assumption H.
Now we assume P is false. Now we have a contradiction - H says that T solves the halting problem, but we know that there is not Turing machine that can solve the halting problem! Thus P must be true!
Notice that P is arbitrary.
Plainly speaking: If you assume that the halting problem can be solved, I can formally prove you that addition does not exist (i.e. there is no operation +, such that it forms a group on Z)
> By the logic (as written) of the article the implication is that '+' does not exist.
This is actually true. With that strong assumption, + does not exist.
If you can implement halt using addition, addition cannot exist.
Ex falso quod libet - if you can prove a single false statement, every statement is true.
In my experience, half opened integer intervals lead to fewer `- 1` in the code.
The referenced issue is only one example. There are many more (e.g. https://github.com/microsoft/vscode/issues/164574).
In case of the merge editor, the diffs should reflect the actual edits as close as possible, so that non-conflicting edits cause non-conflicting diffs, which then allows a non-conflicting merge.
Diffing is hard and there are many subtleties (e.g. https://github.com/microsoft/vscode/issues/164370).
The space efficient Myers diff algorithm has some problems when using it for merging, as tiny changes at the beginning of a file can cause a different path selection later on. Also, Myers doesn't minimize the number of hunks (only their total length), which sometimes leads to unnatural outcomes.
If anybody has good ideas for more advanced diffing algorithms, I'm all ears! (maybe even tree based ones, like difftastic) It's already very difficult to objectively evaluate the quality of a diff or to see if improving the diff for a special case doesn't make the average case worse.
As for the visualization of Myers, I can recommend to have a look at https://blog.robertelder.org/diff-algorithm/.
Rule 30, the collatz conjecture and the monster group let me to the conclusion that even math is chaotic.
Are the algorithms open? Does the tool work reliably?
I find it very sad that potentially revolutionary progress is lost like this...
When you reduce all-pair-shortest-paths (assuming a cubic lower bound) to your problem in quadratic time, your problem has a lower bound of linear time. However, when you speed up the reduction to linear time, your lower bound is quadratic time!
This also applies to simulations of TMs. The faster the simulation, the sharper the complexity classes.
Thus, by making something faster, you can show that something else cannot be made faster anymore.
(Afaik this also applies to P vs NP: Find a fast enough algorithm to reduce an arbitrary problem in EXP to NP and you showed that P!=NP)
The details are described here: https://phiresky.github.io/blog/2022/sqlite-zstd/
This is useful for example when you want to convert between offsets and line/column numbers efficiently, while you also want to efficiently update/insert/replace lines.
When black has a winning strategy, black already applies "zugzwang" for white's very first move: Black only wins because white has to make a move. If white could skip, black would not win.
> Edit: it may be that the statement "without Zugzwang" implicitly (or perhaps by definition) means you are allowed to skip moves?
Yes. It's not well defined, but I'd say a non-zugzwang win is a win (or rather a winning position) where you would also win when your opponent can skip their turn. A zugzwang win is a win that is not a non-zugzwang win.
I would say no by contradiction. Let's assume black could win without zugzwang. Then white would win (and in particular not lose) by skipping the very first move and then playing blacks strategy (because now black has to make the first move and by white skipping the first move, the colors swapped).
If white would not skip the very first move and play an arbitrary move instead, white loses and black wins.
But this is the very definition of zugzwang! Thus, black can only win because of white's initial zugzwang, which contradicts our assumption.
Just like we can efficiently find approximate solutions for the traveling salesman problem (that are at most 50% longer than the optimal solution), these heuristics have not much to do with the optimal solution.
Turing completeness means for TS that for every computable function, there is a TS type that can compute that function (if TS wouldn't limit the recursion depth).
You cannot calculate the expected value (of the envelope you get, when you pick one randomly and then swap) like that, as A is not a constant and actually depends on if you took the less or more valuable envelope initially.
If you use A1=X in case you took the less valuable envelope initially and A2=2X in the other case, the expected value is (1/2)*(2*A1) + (1/2)*(A2/2) = 1.5X
and if you don't swap, you get: (1/2)*A1 + (1/2)*A2 = 1.5X
... which makes sense.
If you change the experiment so that the value of the second envelope does not depend on the first one (if you first chose and only then the value of the other envelope is randomly either double or half), A is constant and you actually should swap.