Bruno Dias

@bruno

"mr storylets"

he/him
brunodias.dev/

writer (derogatory). lead designer on Fallen London.

THESE POSTS ARE PROVIDED “AS IS”, WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE POSTS OR THE USE OR OTHER DEALINGS IN THE POSTS.

Bluesky

brunodias.bsky.social

Letterboxd

letterboxd.com/notbrunoagain/

Backloggd

www.backloggd.com/u/notbrunoagain/

Bruno Dias @bruno10/30/2023, 4:33 PM

Question 1. Read the following statement:

Before you embark on a voyage of revenge, dig n graves.

For any given voyage of revenge, either:

There is a number of graves, n, that can contain all the corpses issuing from that river of blood; or
The number of graves needed is unbounded.

Prove whether for any given voyage of revenge, the boundedness of the number of required graves is decidable. Show your work.

#this was in my drafts I have no idea what I was cooking

You must log in to comment.

in reply to @bruno's post:

@cidolfas10/30/2023, 5:42 PM

Let X be the number of buryable creatures alive at the start of your revenge quest.

Let D be the eventual duration of your revenge quest.

For some amount of time lesser than D - let us call the first span d0 - some amount of new buryable creatures will be born based on the current population. Let us call this x0.

The maximum number of buryable creatures your revenge campaign can kill (or othwise cause a need to bury) at time dt is equal to X + Sum(x0...xt)

There are two cases for the boundaries of D:

D is bound (i.e. "the best Revenge is looking good, and I've got a spa day tomorrow"), in which case n = X + sum(x0...xD)
D is unbound (i.e. "Tell them. Let them flee to the corners of the world in fear. Tell them I'm coming."), in which case n is unbound so long as the function of population birth remains positive
If D is unbound and the rate of new creatures birth can hit 0 beyond some value of dt then n is bound but it sounds annoying to calculate
If D is unbound and the rate of new creatures born between time intervals is negative, then creatures are being unmade through cosmic means. God have mercy on your soul

Caro @caro10/30/2023, 7:20 PM

whyd u hide this gem in the comments

Steven Portzer @sportzer10/30/2023, 6:45 PM

The boundedness of the required number of graves is equivalent to the halting problem, so is not decidable in the general case. For this reason, most general purpose revenge frameworks use some form of dynamic grave management, such as slab allocation.

(Cubone) Kaiz ("Nick") Nike @KaizarNike10/30/2023, 7:44 PM

I hear that's how Dwarf Fortress solved it.

Gravity Pike @gravity-pike10/30/2023, 9:52 PM

Look, we're not dealing with a spherical, frictionless revenant here. The number of graves can always be capped, if not by the campaign of vengence, then by the population in which the campaign operates.

We've got a hard limit of about 8E9 graves. Realistically, there's a much lower soft cap, after which point a population will no longer bother to bury their dead. At a certian point, this becomes a logistics problem, not a math proof.

Pinned Tags