__nobody

A New Paradigm For Emo­tional Work And Men­tal Health

AI Risk Sce­nario Roleplay

• __nobody 26 Aug 2023 12:02 UTC

  3 points

  0

  on: ACX Mee­tups Every­where 2023: Times & Places

  1. In case people want to get to know each other better outside the meetup, you might want to mention reciprocity.io, the rationalist friend-finder/​dating site.

  Unfortunately that requires Facebook =/​ and most of my friends avoid /​ don’t have Facebook for privacy reasons.

  Alternatives:

  • In case you’re on one of the Fletcher-enabled rat Discord servers (like discord.gg/​acx), Fletcher also has a built-in reciprocity feature at https://​​fletcher.fun/​​?view=reciprocity (you’ll need to log in to your Discord account.)

  • …?

• __nobody 10 Sep 2022 19:33 UTC

  12 points

  2

  on: Put Dirty Dishes in the Dishwasher

  Technology Connections viewers already know this somewhat related bit: Consider switching to loose powder instead of tabs, or having both. The dishwasher runs three cleaning cycles (pre-wash, main, rinse), and the tab only goes in for the second phase. The first phase tries to get all the food and grease off using just water… which isn’t ideal. Adding like ¹⁄₂ a teaspoon of the loose powder directly onto the door /​ into the tub at the bottom will greatly support the pre-wash phase and should deal with most things.

  Since I started doing that, I don’t bother scraping at all (obviously? still discarding loose food remains in the bin first) and basically never get stuck bits. (Every couple of months stuff like strongly baked-on cheese from e.g. a gratin may stick to the dish, but that’s it.)

• __nobody 5 Sep 2022 14:41 UTC

  1 point

  0

  on: Pro­to­typ­ing in C

  The way I approach situations like that is to write code in Lua and only push stuff that really has to be fast down to C. (Even C+liblua /​ using a Lua state just as a calling convention is IMHO often nicer than “plain” C. I can’t claim the same for Python...) End result is that most of the code is readable, and usually (i.e. unless I stopped keeping them in sync) the “fast” functions still have a Lua version that permits differential testing.

  Fundamentally agree with the C not C++/​Rust/​… theme though, C is great for this because it doesn’t have tons of checks. (And that’s coming from someone who’s using Coq /​ dependent types regularly, including at work.) Compilers generally want to see that the code is safe under all possible uses, whereas you only care about the specific constellations that you actually use when prototyping. Convincing the compiler, disabling checks, and/​or adding extra boilerplate adds overhead that seriously slows down the process of exploration, which is not something that you want to deal with in that mode.

• __nobody 12 Aug 2022 21:40 UTC

  7 points

  3

  on: What are some good ar­gu­ments against build­ing new nu­clear power plants?

  Sabine Hossenfelder’s assessment (quickly) summarized (and possibly somewhat distorted by that):

  • Uranium 235 is currently used at about 60K tons per year. World reserves are estimated to be 8M tons. Increasing the number of NPPs of current designs by a factor of ~10 means it’s about 15-20 years until it’d no longer be economically viable to mine U235. Combined with the time scales & costs of building & mothballing NPPs, that’s pretty useless. So while some new constructions might make sense, it’s not good as a central pillar of a strategy.

  • Due to the cost of NPP construction etc., nuclear power is way more expensive than all other options. Price of renewables is likely to continue to fall, widening the gap even further. So nuclear is economically very unappealing, and that’s most likely just getting worse with time.

  • Research into new tech takes time (e.g. designs that could use the other 99.3% of available Uranium that’s not U235), and the currently available or soon-to-be available candidates aren’t looking much better, they’re unreliable and/​or likely cost even more (at least initially).

• __nobody 12 Aug 2022 1:44 UTC

  1 point

  0

  on: Pro­posal: Con­sider not us­ing dis­tance-di­rec­tion-di­men­sion words in ab­stract discussions

  This seems to be another case of “reverse advice” for me. I seem to be too formal instead of too lax with these spatial metaphors. I immediately read the birds example as talking about the relative positions and distances along branches of the Phylogenetic tree, your orthogonality description as referring to actual logical independence /​ verifiable orthogonality, and it’s my job to notice hidden interaction and stuff like weird machines and so I’m usually also very aware of that, just by habits kicking in.

  Your post made me realize that instead of people’s models being hard to understand, there simply may not be a model that would admit talking in distances or directions, so I shouldn’t infer too much from what they say. Same for picking out one or more vectors, for me that doesn’t imply that you can move along them (they’re just convenient for describing the space), but others might automatically assume that’s possible.

  As others already brought up, once you’ve gotten rid of the “false” metaphors, try deliberately using the words precisely. If you practice, it becomes pretty easy and automatic over time. Only talk about distances if you actually have a metric space (doesn’t have to be euclidean, sphere surfaces are fine). Only talk about directions that actually make sense (a tree has “up” and “down”, but there’s no inherent order to the branches that would get you something like “left” or “right” until you impose extra structure). And so on… (Also: Spatial thinking is incredibly efficient. If you don’t need time, you can use it as a separate dimension that changes the “landscape” as you move forward/​backward, and you might even manage 2-3 separate “time dimensions” that do different things, giving you fairly intuitive navigation of a 5- or 6-dimensional space. Don’t lightly give up on that.)

  Nitpick: “It makes sense to use ‘continuum’ language”—bad word choice. You’re not talking about the continuum (as in real numbers) but about something like linearity or the ability to repeatedly take small steps and get predictable results. With quantized lengths and energy levels, color isn’t actually a continuous thing, so that’s not the important property. (The continuum is a really really really strange thing that I think a lot of people don’t really understand and casually bring up. Almost all “real numbers” are entirely inaccessible! Because all descriptions of numbers that we can use are finite, you can only ever refer to a countable subset of them, the others are “dark” and for almost all purposes might as well not exist. So usually rational numbers (plus a handful of named constants) are sufficient, especially for practical /​ real world purposes.)

• __nobody 6 Aug 2022 21:06 UTC

  1 point

  in reply to: Ben Pace’s comment on: Book Launch: The Eng­ines of Cognition

  Main constraint you’re not modeling is how increasing margin size increases total pages and thus cost.

  That’s why I’m saying it probably won’t need that for the footers. There’s ~10mm between running footer and text block, if that’s reduced to ~8 or 9mm and those 1-2mm go below the footer instead, that’s still plenty of space to clearly separate the two, while greatly reducing the “falling off the page” feeling. (And the colored bars that mark chapters are fine, no need to touch those.)

• __nobody 6 Aug 2022 20:21 UTC

  3 points

  on: Book Launch: The Eng­ines of Cognition

  Design feedback: Alignment is hard, even when it’s just printing. Consider bumping up the running footer by 1-2mm next time, it ended up uncomfortably close to the bottom edge at times. (Also the chapter end note /​ references pages were a mess.) More details:

  variance: For reference, in the books that I have, the width of the colored bars along the page edge at each chapter (they’re easy to measure) varies between ~4.25mm and ~0.75mm, and sometimes there’s a ~2mm width difference between top and bottom. (No complaints here. The thin /​ rotated ones look a bit awkward if you really look at them, but you’ll likely be distracted by the nice art on the facing page anyway. So who cares, and they do their job.)

  footers: Technically, the footer was always at least 2mm away from the edge (so it didn’t really run the risk of getting cut off), but occasionally it felt so close that it was hard not to notice. That distracted from reading, and made those pages feel uncomfortable… giving it just 1 or 2mm more should take out the tension. (While I didn’t experiment with it, my gut feeling says the text block probably won’t have to move to make more space.)

  end notes/​references: These just looked weird to me. Rambling train of thought style notes:

  • Choice of a different font that looked thin and spindly compared to the main text, worsened by the all-italic choice. (That also made it look fidgety/​restless, thanks to constant kerning weirdness – the font is clearly not meant to be used this way, worst in URLs like Incentives p. 77 item 8.)

  • Usual citation formats are something like ‘Author (Year). “Title.” More stuff.’ or ‘Author (Year). Title. More stuff.‘, so there’s either sufficient punctuation to create noticeable points, or the emphasis creates a texture difference. The chosen ‘Author. Title. Year’ just runs together with no strongly noticeable points, making it hard to pick out the individual fields. It seems to be close to the Bluebook style, but that really relies on the texture contrast in the “Author, Title. Year” to function.

  • The parenthesized item numbering (23) also looked weird in that font, maybe dotted 23. or 23: would have looked better; combined with the numbers being the only thing not italicized, it looked more like a mistake than intention to me.

  • Also lots of typos /​ inconsistencies, e.g. occasional missing years/​dates, sometimes it’s just “Wikipedia. Article name.” (good IMHO) then sometimes it’s “Article. Wikipedia” (why is the “author” not first here?) and sometimes it’s a badly-formatted link (whyyy), occasionally it looks like there’s two spaces instead of one (or just more kerning weirdness?), and e.g. Incentives p. 206 has items 4 + 5 running into each other.

  • Some indication for where the text can be found would be helpful. (Also whether it’s a text or something else.) Most seem to be on LW, some can be guessed, but for others you have to search. Shorthands like e.g. a ° after the title to mark “this is on LW” or maybe a small ˣ for “can be found in arXiv” would be enough for the usual sources. But try finding Incentives p 133 item (10) by searching! The only way to find it is to look up the original article, locate the link, and then facepalm hard at the incomplete information.

  • It all seemed more like an afterthought than a planned part of the book, and the look of the whole really encouraged me to quickly turn to the next page, instead of looking for more things to read.

  • (Also: Consider reducing the line height and item spacing? It’s not text that you read continuously, so less leading both reduces the required space and makes it stand apart from the main text without using questionable fonts.)

  Apart from that, I loved the design! Thanks to everyone involved for making the books, they’re lovely! <3

• __nobody 21 Jul 2022 0:11 UTC

  3 points

  0

  on: Ap­pli­ca­tions are open for CFAR work­shops in Prague this fall!

  Sounds great so far, some questions:

  • How does travel work? Do you get to Prague on your own and then there’s organized transport for the last leg, or do you have to do the whole journey yourself? (I don’t drive /​ only use public transport. Car-less travel to “a village about 90 mins [by car?] from Prague” could be anywhere between slightly annoying and near-impossible.)

  • How does accommodation & food work?

  And (different category)

  • Are some of you at LWCW to chat in person?

• __nobody 17 Jul 2022 17:49 UTC

  11 points

  0

  on: Po­tato diet: A post mortem and an an­swer to SMTM’s article

  Re solanine poisoning, just based on what’s written in Wikipedia:

  Solanine Poisoning /​ Symptoms

  [...] One study suggests that doses of 2 to 5 mg/​kg of body weight can cause toxic symptoms, and doses of 3 to 6 mg/​kg of body weight can be fatal.[5][...]

  Safety /​ Suggested limits on consumption of solanine

  The average consumption of potatoes in the U.S. is estimated to be about 167 g of potatoes per day per person.[11] There is variation in glycoalkaloid levels in different types of potatoes, but potato farmers aim to keep solanine levels below 0.2 mg/​g.[18] Signs of solanine poisoning have been linked to eating potatoes with solanine concentrations of between 0.1 and 0.4 mg per gram of potato.[18] The average potato has 0.075 mg solanine/​g potato, which is equal to about 0.18 mg/​kg based on average daily potato consumption.[19]

  Calculations have shown that 2 to 5 mg/​kg of body weight is the likely toxic dose of glycoalkaloids like solanine in humans, with 3 to 6 mg/​kg constituting the fatal dose.[20] Other studies have shown that symptoms of toxicity were observed with consumption of even 1 mg/​kg.[11]

  If 0.18 mg/​kg = 167 g of Potatoes, then 1 g/​kg is reached at 927g of potatoes, which equals about 800 calories. So if you “eat as much as you want”, I’m not surprised at all if people show solanine poisoning symptoms.

  (And that’s still ignoring probable accumulation over prolonged time of high consumption.)

• __nobody 8 Jul 2022 16:21 UTC

  6 points

  1

  in reply to: Michael Harrop’s comment on: Be­ing a donor for Fe­cal Micro­biota Trans­plants (FMT): Do good & earn easy money (up to 180k/​y)

  My gut feeling (no pun intended) says the mythical “super-donor” is a very good excuse to keep looking /​ trying without having to present better results, and may never be found. Doing the search directly in the “microbiome composition space” instead of doing it on people (thereby indirectly sampling the space) feels way more efficient, assuming it is tractable at all.

  If some people are already looking into synthesis, is there anything happening in the direction of “extrapolating” towards better samples? (I.e. take several good-but-not-great donors that fall short in different ways, look at what’s same /​ different between their microbiome, then experiment with compositions that ought to be better according the current understanding, and repeat.)

• __nobody 1 Jul 2022 23:52 UTC

  4 points

  3

  in reply to: Lone Pine’s comment on: Challenge: A Much More Alien Message

  I have something in the pipeline, but it’ll take a while… if it’s trying to be “actually” alien, it’s kinda important that it’s internally consistent. “Add some arbitrary bytes to [...represent] metadata” is exactly what you don’t want to do. Because if you do, sure, it’ll be hard, it’ll (probably) be eventually solvable, but it’ll be… somewhat dissatisfying. Same for using stuff like NTSC, it’s just… why would they come up with exactly that? It just doesn’t make any sense!

  So, in case anyone else wants to also make a good challenge in this style, here’s some guidelines. The first and most important one:

  • Ensure that every. single. layer. has some clearly recognizable artifact /​ regularity. Blocks + checksums, pilot tones, carrier waves, whatever. It can occasionally be rather obscure /​ hard to identify, but never completely absent. If you have to get through ≈10 layers of stuff to solve the whole thing, getting stuck for a few hours (or even days) with no indication of whether you’re even heading in the right direction is very unsexy and will likely kill the mood. (It’s also internally consistent w.r.t. the back story of an alien message: For an intentional transmission, they want you to understand what they’re sending. Even an accidental or amateur message would likely use (their) standard protocols /​ file formats, which will likely have some regularity – headers, blocks, trailers, … – because that makes it easier to debug problems.)

  The rest falls into the “do some world building” and “ensure internal consistency” buckets:

  • Weird senses are cool, not everyone needs to have a focus on vision, especially not on exactly 3 types of receptors focusing on exactly the same 400–700 nm range as we do – the electromagnetic spectrum is way larger. (Even animals already have pretty crazy stuff going on!) Vision doesn’t have to be the primary sense (with low-resolution “eyes”, other senses may be preferable.) Having a two-dimensional arrangement of identical building blocks (a.k.a. “images” made of “pixels”) isn’t necessarily ideal for all senses. Different senses likely also result in other things being obvious, considered likely or unlikely, or being missed entirely when trying to find message formats that are most widely understood. (Beings whose senses revolve entirely around sound and movements may not have static things like books or writing at all, a cave-dwelling culture near a very aggressive star may consider all EM /​ “light” exposure as dangerous or deadly (compare: the popular image of radioactivity for us) and strongly avoid developments in that direction.)

  • Try not to copy “historical accidents” blindly. Most existing media formats are harshly optimized towards being barely good enough to fool human senses. (Especially lossy compression generally exploits shortcomings of human senses to remove stuff that we would be unable to sense in the presence of stronger surrounding stimuli, but even simple “lossless” formats are generally human-centric. Historically, memory/​storage was not cheap at all, and you really wanted to get the most out of your bits.) An alien message will likely try to avoid optimizing in the wrong way, but may well fail at that in interesting ways.
    RGB bakes material properties and lighting into just three numbers and ignores all other things, even though we are able to see e.g. metamerism effects in the real world. Stereo audio bakes sound waves into two channels, even though we can detect much more finely where sounds are coming from in the real world. (Your very personal ear shape influences how things sound coming from different directions, so while you can shove approximate directions and distances into two channels, it sounds quite different from what you’re used to in the real world.) Different priorities will result in different trade-offs.
    Even for computers, binary isn’t required. (There were decimal computers, that’s just way more complex than 2 states and so eventually that won out. If the prevailing number base is 3 or 4 instead of 10, that’s much more doable.) Same goes for 8-bit groups as the next building block. (16 is “more square” and behaves nicer in some contexts. But we also had what’s basically 9-bit computers, that were using a 36-bit word size, so the next level of grouping doesn’t have to cleanly divide at all. It also provides space for e.g. a parity bit if you do want to stick to “base-powered” block sizes.)

  • Look at how things would actually transmit – you don’t get a convenient blob of bits. (That would already lock in a binary base, potentially bytes as the next level too, making it much harder to do actual fun stuff with weird senses.) Actually, you’d get some noisy recording (likely with burst errors blotting out information here and there) from which you have to recover the frequency at which symbols are coded, then recover that sequence and try to recognize and fix errors, and so on… beyond parity bits, there’s full error correction codes, interleaving, and all the rest of coding theory. You may want to repeat the same message in a loop, or have a sequence of messages to make it easier to decode the main message (e.g. stylized geometric shapes, simple but anisotropic patterns, or chirps to help fix directions and scales before the “messy” recorded data like images or sound.)

  ...and so on like that, but I hope that’s enough to send anyone considering to make such a challenge at the “actual” alien message level in approximately the right direction. Eagerly anticipating silly alien selfies! ;)

• __nobody 12 Mar 2022 14:46 UTC

  5 points

  in reply to: Yitz’s comment on: In­fo­haz­ards, hack­ing, and Brick­ing—how to for­mal­ize these con­cepts?

  I can’t recall specific names /​ specific treatments of this, but I’m also relatively sure that it’s kinda familiar, so I suspect that something exists there. Problem is that, in some sense, it falls right between areas.

  On the practical side, people don’t really care where the problem originates, they just want to fix it. (And people are swimming in abstraction layers and navigate them intuitively, so a “this is one layer up” doesn’t really stand out, as it’s still the bottom layer of some other abstraction.) So from the perspective of computer security, it just falls into the big bucket of what’s called a “denial of service” vulnerability (among lots of other things like just temporarily slowing things down, or making a system do 2^51 compute steps (i.e. locking it up effectively forever but not “truly” forever) or making it drown in traffic from outside), but there’s generally no category separation between “possible bugs” (that just happen to be in one specific implementation) and “necessary bugs” (the “logic bugs” that are in the spec, where every conforming program will end up with the same problem.)

  On the theoretical side, you mostly work with bounded recursion instead of possibly unbounded loops, so the problem is more-or-less impossible. (And while Turing machines exist on the theory side too, working with them sucks so it doesn’t really happen a lot, so people don’t really notice problems that occur when working with them. And so it’s mostly bounded recursion.) As an example, if you write your program in Coq, you’re forced to prove that every recursive computation terminates in order to be allowed to compile (and run) your program. So as soon as you care even a little about verification, the problem basically disappears /​ becomes invisible. In theory, the path to reaching a fixed point by reacting to each input in exactly the same way is still open (by messing up your state), but that’s very unlikely to hit by chance (especially if you write in the typical stateless style), so people might not stumble on that ever, so the chances of thorough exploration are rather low too. (Still feels like there was something, somewhere...)

  In other areas:

  • From the perspective of dynamical systems, it’s just a fixed point.

  • In temporal logic, it’s something that would be happening “eventually forever”.

  If you can’t find anything after using that to find more keywords, I’d suggest you ask someone at the Santa Fe Institute, they do lots of dynamical systems stuff, and if it exists at all, there’s a pretty good chance that someone there has heard of it. (I’ve seen them mention kinda nearby concepts in one of the “Complexity Explorer” courses. According to that page, Cristopher Moore does a computability etc. course soon-ish, so he should either be the right person to ask or know who to forward it to.)

• __nobody 10 Mar 2022 22:09 UTC

  7 points

  on: In­fo­haz­ards, hack­ing, and Brick­ing—how to for­mal­ize these con­cepts?

  Some very quick notes, don’t have time for more:

  • It looks to me as if you fail to separate formal models from concrete implementations. Most exploitability results from mismatches between the two. As a concrete example, the PDF spec says (said?) that a PDF starts with a “this is a PDF” comment, e.g. %PDF-1.4. (Right at the start, with nothing before it.) In practice, most readers are happy if that signature sits anywhere in the first 4KiB or something like that. End result are benign things like polyglot files on the one end – look for Ange Albertini and/​or the International Journal of PoC||GTFO (“Proof-of-Concept or Get The F*** Out”) – or malicious results like your [guard mechanism – firewall/​antivirus/​…] parsing things one way and considering them safe, and [target program] parsing them in another way and [blowing up – crashing /​ running embedded code /​ …]. As long as you only look at specs /​ formal models, you cannot talk about the actual effects. You have to actually look at the code /​ program, have to get down to the base level, to see these problems.

  • For more stuff on that look at LANGSEC (very short summary, but the papers quite are readable too) or the stuff that Halvar Flake does. Briefly and slightly over-simplified, the model here is that you have a universal machine (your computer) but want it to do a very specific limited thing, so you write an emulator (your program) for a finite state machine or similar. There are certain state transitions implemented by your code, and the program starts out in a “sane” state. Certain events (weird inputs, memory manipulation, …) might move the program from a sane state into a “weird state”, and after that you can still trigger the transitions intended for sane states, but instead they are run on weird states – you now have a “weird machine” that does unintended things. Another key insight from the LANGSEC stuff is that you write the program, so you probably think you decide what’s going to happen, but actually the program is effectively an interpreter for the input that behaves like a program running on your “interpreter”, so whoever provides the input (files, network packets, …) actually decides what happens. (Within the bounds set by your code, but those are often uncomfortably loose.) Not only is code data (as taught by Lisp), but data is also code.

  • Formal models can’t be exploitable in this sense, as they are the specification. What can happen is that there’s logic bugs in the spec, but that is a very different class of problems. So an abstract Turing machine can’t really be hackable as it will behave exactly according to specification (as it is the spec), the program implemented by the TM might be faulty and exploitable, and a concrete implementation of the TM might be too. (Of course, logic bugs can also be very very bad.)

• __nobody 28 Feb 2022 11:30 UTC

  1 point

  on: Nudg­ing My Way Out Of The In­tel­lec­tual Mosh Pit

  On the topic of grayscale: Love it, strongly recommend trying to everyone too.

  What I’d really like to see is a way to selectively grayscale applications, or exclude some from the grayscale filter. (So e.g. if I’m running Gimp/​PS/​..., keep just that one non-grayscale while still desaturating everything else.) If anyone knows anything, all pointers are strongly appreciated!

  (I think it ought to be possible with the X server permissions model on Linux, but I’m not sure if a program could even have the permissions to do this on Windows.)

• __nobody 26 Feb 2022 13:58 UTC

  2 points

  in reply to: Alicorn’s comment on: Train­ing My Friend to Cook

  I’ve done both – asparagus and lettuce – and it works. (Especially for the more bitter kinds of leafy greens, it somewhat reduces bitterness. It can also soften the stems /​ bottom bits and make them more usable. So e.g. finely chopping the stem and sauteing with some onion and mushrooms can be a good way to use what you’d otherwise discard.)

  There’s even salad-based soups (both with something like e.g. romaine added just before the end, and also with e. g. iceberg shredded, cooked, and blended), and while it may seem strange initially and mess with your expectations, they work just fine. (The end result doesn’t match “what salad is supposed to be like”, so the gut reaction for many is to reject it. But actually it’s just leafy greens.)

• __nobody 10 Feb 2022 16:14 UTC

  2 points

  on: Bet on Rare Un­de­sir­able Out­comes when Seed­ing a Pre­dic­tion Market

  Typo: “Prediction markets require liquidity. Suppose you seeded your prediction market with $10,000 of liquidity such that an investor can invest $10,000 into the market without noticeably moving the prices.”

  That number is wrong, and I’m not entirely sure which one was intended.

• __nobody 28 Jan 2022 9:56 UTC

  3 points

  in reply to: Morpheus’s comment on: What is the ev­i­dence on the Church-Tur­ing Th­e­sis?

  They’re actually quite different from how our computers work (just on the surface already, the program is unmodifiable and separate from the code, and the whole walking around is also a very important difference^[1]), but I agree that they feel “electronics-y” /​ like a big ball of wires.

  Don’t forget that most of the complexity theoretic definitions are based on Turing machines, because that happened to become the dominant model for the study of these kinds of things. Similar-but-slightly-different constructions would perhaps be more “natural” on lambda calculus, so if that had been the dominant model, then the Turing machine versions would have been slightly awkward instead.

  But memory isn’t actually a problem – see Lisp. Represent everything as a cons cell (a storage unit with two slots) or a “symbol” (basically an unmodifiable string that compares in O(1)), where cons cells nest arbitrarily. (Simplest cell representation is two pointers and maybe a few tag bits to decide what it represents… optionally plus garbage collector stuff. Very close to how our computers operate!) Variable names become symbols, application becomes a cell, and lambdas can either become a specially tagged cell, or a nested construction like (lambda ('var body)) (doesn’t really make a difference memory-wise, just a constant factor.) Time is also easy – just count the number of reductions, or maybe include the number of substitutions if you think that’s important. (But again, constant factor, doesn’t actually matter.)

  You could even argue that the problem goes in the other direction: For Turing machines, you largely don’t care about the states (often you don’t even explicitly construct them, just argue that they could be constructed), whereas lambda calculus programs are routinely written out in full. So had lambda calculus become the basis, then program size /​ “problem description complexity”, the “cost of abstractions”, reusability and other related things might have been considered more important. (You get a bit of that now, under the name of “code quality”, but it could have happened much earlier and way more thoroughly.)

  ---

  1. ↩︎

     An average normal program is extremely pointer-heavy, but you don’t even have the “alphabet” to efficiently represent pointers. (Unless you make “bytes” from bits and then multiply your state count to deal with that construction.) You also don’t have absolute locations, you can’t really do variables (especially not arbitrary numbers of them), and so on. So if you look deeper, both have a very different approach to state and, by extension, functions.

• __nobody 24 Jan 2022 22:11 UTC

  6 points

  on: What is the ev­i­dence on the Church-Tur­ing Th­e­sis?

  I’ll focus on the gears-level elaboration of why all those computational mechanisms are equivalent. In short: If you want to actually get anything done, Turing machines suck! They’re painful to use, and that makes it hard to get insight by experimenting with them. Lambda calculus /​ combinator calculi are way better for actually seeing why this general equivalence is probably true, and then afterwards you can link that back to TMs. (But, if at all possible, don’t start with them!)

  Sure, in some sense Turing machines are “natural” or “obvious”: If you start from finite state machines and add a stack, you get a push-down automaton. Do it again, and you essentially have a Turing machine. (Each stack is one end of the infinite tape.) There’s more bookkeeping involved to properly handle “underflows” (when you reach the bottom of a stack and need to extend it) yadda yadda, so every “logical state” would require a whole group of states to actually implement, but that’s a boring mechanical transformation. So just slap another layer of abstraction on it and don’t actually work with 2-stack PDAs, and you’re golden, right? Right…?

  Well… actually the same problem repeats again and again. TMs are just extremely low-level and not amenable to abstraction. By default, you get two tape symbols. If you need more, you can emulate those, which will require multiple “implementation states” to implement a single “logical state”, so you add another layer of abstraction… Same with multiple tapes or whatever else you need. But you’re still stuck in ugly implementation details, because you need to move the head left and right to skip across stuff, and you can’t really abstract that away. (Likewise, chaining TMs or using one as a “subroutine” from another isn’t easily possible and involves lots of manual “rewiring”.) So except for trivial examples, actually working with Turing machines is extremely painful. It’s not surprising that it’s really hard to see why they should be able to run all effectively computable functions.

  Enter lambda calculus. It’s basically just functions, on a purely syntactic level. You have binders or (anonymous) function definitions – the eponymous lambdas. You have variables, and you have nested application of variables and terms (just like you’re used to from normal functions.) There’s exactly one rule: If a function is applied to an argument, you substitute that argument into the body wherever the placeholder variable was used. So e.g. (λx.((fx)y)(gx))z → ((fz)y)(gz) by substituting z for x. (Actual use of lambda calculus needs a few more rules: You have to make sure that you’re not aliasing variables and changing the meaning, but that’s a relatively minor (if tricky) bookkeeping problem that does abstract away fairly cleanly.)

  Now, on top of that, you can quickly build a comfortable working environment. Want to actually name things?let x := y in t is just a ((λx.t)y). (The assignment being split around the whole code is a bit ugly, but you don’t even need “actual” extensions, it’s just syntax sugar.) Data can also be emulated quite comfortably, if you understand one key idea: Data is only useful because you eventually do something with it. If all you have is abstraction, just abstract out the “actually doing” part with a placeholder in the most general scheme that you could possibly need. (Generally an induction scheme or “fold”.) [Note: I’ll mostly use actual names instead of one-letter variables going forward, and may drop extra parentheses: f x y z = (((f x) y) z)]

  • In a way, Booleans are binary decisions. true := λtt.λff.tt, false := λtt.λff.ff (Now your if c then x else y just becomes a c x y… or you add some syntax sugar.)

  • In a way, natural numbers are iteration. zero := λze.λsu.ze, succ := λn.λze.λsu.su(n ze su). (If you look closely, that’s just the induction principle. And all that the number “does” is: (succ (succ (succ zero)) x f) = f (f (f x)))

  • Lists are just natural numbers “with ornaments”, a value dangling on every node. nil := λni.λco.ni, cons := λx.λxs.λni.λco.co x (xs ni co) The usual list functions are easy too: map := λf.λxs.(xs nil (λx.λxs.cons (f x) xs)), fold := λxs.xs (yep, the list – as represented – is the fold)

  And so on… so I think you’ll believe me that you basically have a full functional programming language, and that lambda calculus is equivalent to all those more usual computational substrates. (…and maybe Turing machines too?)

  Still… even if lambda calculus is extremely simple in some ways, it’s also disturbingly complex in others. Substitution everywhere inside a term is “spooky action at a distance”, a priori it’s quite plausible that this does a lot of “heavy lifting”. So: Let’s turn to combinator calculi. Let’s keep the term structure and application of things, but get rid of all (object-level) variables and binders. Instead, we define three substitution rules: (using variables only at the meta-level)

  • I x = x

  • K v x = v (or, fully parenthesized: (K v) x = v)

  • S a b x = (a x) (b x) (or, again more precisely: ((S a) b) x = (a x) (b x))

  (Strictly speaking, we don’t even need I, as SKKx = (Kx)(Kx) = x, so if we say I := SKK that’s equivalent.) The interesting thing about these rules is that all lambda-terms can be translated into SKI-terms. (To get rid of a binder /​ λ, you recursively transform the body: Pretend the intended argument x is already applied to the body, how do you get it where it needs to go? If you have an application, you prefix it with S such that the argument is passed down into both branches. If a branch doesn’t use the argument (that includes other variables), prefix it with K so it remains unchanged. Otherwise, it is the bound variable that should be substituted, so put an I and you get the value. Done.) Worst case, this will cause an exponential(!) increase of the term size, but it’ll get the job done. After that, there’s no more “looking inside terms” or dealing with variables, but extremely simple rewrite rules. To revisit the examples above:

  • true := λtt.λff.tt → λtt.(K tt) → S(KK)I, false := λtt.λff.ff → λtt.(I) → KI

  • zero := λze.λsu.ze → S(KK)I, succ := λn.λze.λsu.su(n ze su) → λn.λze.SI(S(K(n ze))I) → λn.S(K(SI))(S(S(KS)(S(KK)(S(KK)(S(K n)I)))(KI)) → (S(K(S(K(SI))))(S(S(KS)(S(K(S(KS)))(S(K(S(KK)))(S(S(KS)(S(KK)I))(KI)))))(K(KI)))) […except I think I messed up somewhere.]

  • (And yes, I did that by hand… so I hope you’ll accept that I stop there and don’t translate the other examples.)

  So actually you don’t need lambda calculus (or variables, for that matter), just these two rules. You can compile your Haskell to this SKI-stuff.

  Take a moment to process that.

  Now I hope it’s also pretty obvious that you can implement a Turing machine in Haskell? Same for imperative programming languages – look at e.g. the Whitespace interpreter (Haskell version in the archive, Idris version on Github). So at this point I think you have a pretty good intuition as for why all existing computational mechanisms can be reduced down to SKI-calculus.

  As for the other direction…with a basic TM model, dealing with all those dynamically resizing parts would be extremely painful, but if you use an extended Turing machine that has lots of different symbols and also more than one band, it’s actually not that hard? Detecting expandable locations isn’t that hard if you use one band as scratch space for counting nested parentheses. Doing the “reductions” (which can actually greatly expand the space needed because S duplicates the argument) can also happen on a separate band, and then afterwards you copy over the stuff back onto the “main band”, after adjusting the placement of the unchanged stuff on the side. (I hope that’s sufficiently clear? This is basically using multiple bands as a fixed number of temporary helper variables.)

  And that’s it. Now you can run your Turing machine in your Haskell on your Turing machine, or whatever… Hope you’re having fun!

  What links here?

  • __nobody's comment on In­fo­haz­ards, hack­ing, and Brick­ing—how to for­mal­ize these con­cepts? by Yitz (12 Mar 2022 14:46 UTC; 5 points)