tromp

It can be solved if the memory is bounded. But unbounded memory comes with undecidable problems.

This is like Proof-of-Work, but for an extremely small amount of work, that would already overwhelm human effort, like computing a single SHA256.

Every single cryptocurrency (except one or two) concentrates wealth on the founders and early adopters.

In France, Germany, Austria, Switzerland, the Low Countries, Ireland and Scandinavia, however

What are the Low Countries? Is that a mis-translation of the Netherlands?

Meanwhile, a single human cell's DNA stretches for about 2 meter, one human's DNA stretches for about 2 x 5.4 trillion meter, and all living human DNA for a whopping 8.6 x 10^22 meters, nearly a thousand times longer than the fungi networks...

[1] https://www.reddit.com/r/theydidthemath/comments/1gfq6k2/how...

Shor doesn't solve an NP hard problem. It's even possible that factoring and discrete log are in P, while P != NP.

The paper builds on the results of "Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems" by Abrams and Loyd [1], from which I quote:

The last qubit now contains all the information that we need; however, for small s, a measurement of the last qubit will almost always return |0>, yielding no information. We wish to distinguish between the cases s=0 and s>0.

Step 4. Repeatedly apply the nonlinear operation to drive the states representing these two cases apart at an exponential rate: eventually, at a time determined by a polynomial function of the number of qubits n, the number of solutions s, and the rate of spreading (Lyapunov exponent) λ, the two cases will become macroscopically distinguishable.

[1] https://arxiv.org/abs/quant-ph/9801041

I think Oppo is the first to visibly eliminate the crease with their Find N6.

https://www.pcmag.com/news/i-tried-oppos-latest-foldable-pho...

One of the main instruments of obfuscation (and the way to get more out of the size constraints) is making the code as short as possible, so in that example you'd prefer

    if (!(x/2-1)) { ...

And how diamonds are grown: https://en.wikipedia.org/wiki/Synthetic_diamond

https://archive.is/SafF7

https://en.wikipedia.org/wiki/Capture_the_flag_(cybersecurit...

still has no mention of AI, but that will likely change as they increasingly dominate competition.

The author presents most known numeral systems (ways of representing natural numbers) in lambda calculus, classified by whether the term use their bound variables exactly one time (linear), at most one time (affine), or multiple times (non-linear). Mackie's paper [0] (one of the references) provides a good introduction to these. (although he strangely gets the definition of Church numerals wrong with "Church numerals encode numbers with repeated application: λx f. f^n x." in which he reversed the order of arguments f and x).

He illustrates some numerals in each system with a graphical notation that strongly reminds me of interaction nets [1], a computational model closely related to lambda calculus. The notation they use for lambda terms is rather non-standard. Compare

In β-reduction, k[(x⇒b)←a]⊳k[b{a/x}]k[(x⇒b)←a]⊳k[b{a/x}]

with Wikipedia's [2]

The β-reduction rule states that a β-redex, an application of the form (λx. t) s, reduces to the term t[x:=s].

The k[...] part means that β-reduction steps can happen in arbitrary contexts.

[0] https://www.researchgate.net/publication/323000057_Linear_Nu...

[1] https://en.wikipedia.org/wiki/Interaction_nets

[2] https://en.wikipedia.org/wiki/Lambda_calculus

The task is to place four black queens and one black bishop on the chessboard so that there is no square not under their attack. In other words, after arranging the five black pieces, it must be impossible to place the white king anywhere without it being in checkmate.

That last word should be "check". not "checkmate". A king next to an unprotected queen will be in check but not checkmate as it can capture the queen.

fly two to three times faster (about 460 miles per hour, compared to 90 miles per hour)

Is this AI math? That's over 5 times faster.

Next Friday always means the Friday after the next one

You're using "the next one" i.e. the next Friday, to refer to the first one after today.

Except on Friday's, when "this Friday" means today. On other days, many people indeed use "this" and "next" synonymously.

The Simple Rule

If the Friday you’re referring to is beyond seven days from today, including today, it’s next Friday.

That's not a such simple rule. I'm not even sure what "including today" means.

A simple rule would be: next Friday is the first Friday after today.

The whole existence of this website suggests that the term "Next Friday" is at best ambiguous. Especially on a Saturday or Sunday, many people will interpret "Next Friday" as the Friday of next week. So just be explicit and say "Friday next week".

One of the smallest implementations is my heavily obfuscated https://www.ioccc.org/2012/tromp/ :

           Int L[A],m,b,*D=A,
            *c,*a=L,C,*U=L,u;s
             (_){u--&&s(a=*a);}
              char*B,I,O;S(){b=b
               --?b:m|read(0,&I,1
                )-1;return~I>>b&1;
                 }k(l,u){for(;l<=u;
                  U-L<A?*U++=46^l++[
                   "-,&,,/.--/,:-,'/"
                   ".-,-,,/.-,*,//..,"
                  ]:exit(5));}p(Int*m){
                 return!*U?*m=S()?U++,!S
                ()?m[1]=p(++U),2:3:1,p(U)
               :S()?U+=2:p(U[1]++),U-m;}x(
              c){k(7*!b,9);*U++=b&&S();c&&x
             (b);}d(Int*l){--l[1]||d(l[d(*l),
            *l=B,B=l,2]);}main(e){for(k(10,33
           ),a[4]-=m=e-2&7,a[23]=p(U),b=0;;e-2
          ?e?e-3?s(D=a),C=a  [3],++1[a=a[2]],d(
         D):c?D=c,c=*D,*D=    a,a=D:exit(L[C+1])
        :C--<23?C=u+m&1?O      =O+O|C&1,9:write(m
       ||(O=C+28),&O,1)+        1:(S(),x(0<b++?k(0,
      6),U[-5]=96:0)):(          D=B?B:calloc(4,X))
     ?B=*D,*D=c,c=D,D[            2]=a,a[++D[1]]++,D
    [3]=++C+u:exit(6)              )e=L[C++],u=L[C];}

Alonzo Church developed the lambda calculus in 1929.

His first publication that showed the elements of the lambda calculus was the 1932 paper "A set of postulates for the foundation of logic", as I cited in my recent paper [1]. It's quite possible he worked on it prior to 1932, but I don't know of any credible evidence on that (would be very interested to learn about any).

Wait! How the heck is this a "programming" language? At first glance, this simple language seems to lack both recursion and iteration, not to mention numbers, booleans, conditionals, data structures and all the rest. How can this language possibly be general-purpose?

What most stops lambda calculus from being a programming language is that it doesn't directly support I/O. However, one can adopt some very simple conventions for representing bits, lists of bits (bytes), and lists of bytes, and for letting a lambda term operate on these [2] which make the so-called Binary Lambda Calculus (BLC) a programming language.

And a very expressive language it is too: a BLC self interpreter [4] can be as small as the 170-bits

    01000110100001000
    00001100000010111
    00110000111111100
    00101110011111110
    00000111100000010
    11101110011011110
    01111111100001111
    11110000101111010
    01110100101111101
    00101101010011010

 which encodes the term

    (λ11)(λ(λλλ1(λλ2(1(λ6(λ2(6(λλ3(λλ23(14))))(7(λ7(λ31(21)))))))(41(111))))(11))

    ┬─┬ ────────────────────────────────────────────┬─┬
    └─┤ ──────┬───────────────┬──────────────────── ├─┘
      │ ──────┼───┬───────────┼─┬─────────┬──────── │
      │ ┬─────┼───┼───────────┼─┼─────────┼──────── │
      │ │ ┬───┼───┼───────────┼─┼─────────┼──────── │
      │ │ ┼─┬─┼───┼───────────┼─┼─────────┼─┬─┬─┬─┬ │
      │ │ │ │ ┼─┬─┼───────────┼─┼──────── └─┤ └─┤ │ │
      │ │ │ │ │ ┼─┼─┬─────────┼─┼─┬──────   │   ├─┘ │
      │ │ │ │ │ │ │ ┼───────┬ │ ┼─┼───┬──   ├───┘   │
      │ │ │ │ │ │ │ ┼───┬───┼ │ │ ┼─┬─┼─┬   │       │
      │ │ │ │ │ │ │ │ ┬─┼───┼ │ │ └─┤ ├─┘   │       │
      │ │ │ │ │ │ │ │ ┼─┼─┬─┼ │ │   ├─┘     │       │
      │ │ │ │ │ │ │ │ └─┤ ├─┘ │ ├───┘       │       │
      │ │ │ │ │ │ │ │   ├─┘   ├─┘           │       │
      │ │ │ │ │ │ │ ├───┘     │             │       │
      │ │ │ │ │ │ ├─┘         │             │       │
      │ │ │ │ │ └─┤           │             │       │
      │ │ │ │ │   ├───────────┘             │       │
      │ │ │ │ ├───┘                         │       │
      │ │ │ ├─┘                             │       │
      │ │ └─┤                               │       │
      │ │   ├───────────────────────────────┘       │
      │ └───┤                                       │
      │     ├───────────────────────────────────────┘
      └─────┘

    (define (eval e env) (cond
      ((symbol? e)       (cadr (assq e env)))
      ((eq? (car e) 'λ)  (cons e env))
      (else              (apply (eval (car e) env) (eval (cadr e) env)))))
    (define (apply f x)
      (eval (cddr (car f)) (cons (list (cadr (car f)) x) (cdr f))))
    (display (eval (read) '())) (newline)

Except that it leaves all the actual parsing to the "read" library function.

In contrast, the BLC code does all parsing itself. One of the neatest tricks is how it represents the environment as a list built with

      cons' =  \x\y\zx\zy. zx x (zy y)

[1] https://www.mdpi.com/1099-4300/28/5/494 "The Largest Number Representable in 64 Bits"

[2] https://gist.github.com/tromp/86b3184f852f65bfb814e3ab0987d8...

[3] https://tromp.github.io/cl/diagrams.html

[4] https://github.com/tromp/AIT/blob/master/ait/int.lam

The build process: https://www.youtube.com/watch?v=HzI2GgTZAfE

Design of this (not quite) unpickable lock: https://www.youtube.com/watch?v=-qUu8kIliy8

import Control.Monad (guard)

"fizz" <$ guard (rem i 3 == 0)

I prefer the more transparent

    if i `mod` 3 == 0 then Just "fizz" else Nothing

But the value of a 51% attack is roughly proportional to marketcap, so while they are cheaper to attack, there's less incentive for the attack. The most (relatively) vulnerable coins are those where the daily dollar value is low relative to the market cap.

By having a small daily dollar value (the column "PoW Produced (24h) in [1]). All but the top 15 coins sorted by that column have less than $10k emitted per day in block rewards, which limits the power that miners can spend on competing for it.

[1] https://www.f2pool.com/coins

Correct; both Bitcoin and Monero use Hashcash as PoW, only differing in the choice of hash function. Verification is only different from a solution attempt in asymmetric (i.e. non-Hashcash) PoW, such as Cuckoo Cycle or (the poorly named) Equihash.

A similar Haskell success story (from Bellroy) is the subject of an upcoming Melbourne Compose meeting: https://luma.com/uhdgct1v

just none are good for you and all lead to a loss given perfect play.

That's exactly what it means to be in a lost position; all moves lose. A lost position is only Zugzwang though if the same position with the opponent to move is not lost.

While normal Go allows passing one's turn, and thus has no zugzwang, there is a No Pass Go variant [1] that forbids passing, where the first player in zugzwang loses the game.

[1] https://senseis.xmp.net/?NoPassGo

You run out of time on your clock. If you press your clock without moving, the opponent will alert the referee to sort you out. And if you play without a clock, your opponent will get annoyed at you taking forever to move.

In 2010, Prime Minister David Cameron told an Indian television show that returning the diamond would set a dangerous precedent. “What tends to happen with these questions is that, if you say yes to one, you suddenly find the British Museum would be empty,” he told New Delhi Television.

Emptying the British museum of all its looted treasure is quite a noble goal.

As is emptying Gitmo of all its illegally held prisoners.