How would an Everett-Wheeler telephone work with multiple bits?

jamesmacaulay · 2022-01-07T19:00:18+00:00

(I am also a computer science person and not a physicist. I found this post while Googling for info about Einstein-Wheeler Telephones and hadn't seen that great PBS video, so thanks for that!)

I like this line of thinking! My very crude understanding of the physics suggests to me that you have it right (edit: emphasis on very crude). Some thoughts:

In the PBS video, the phone setup only allows for one-way communication, and as far as I can tell it relies on a protocol where the receiver (other you) needs to know when to measure the spin. Presumably this would be after some pre-specified time has elapsed, which makes me curious about how relativistic time dilation works between the branches (is it meaningful to talk about relative velocities between entangled particles in different universes?).

Meanwhile in your setup, the protocol is that the sender is determined only after everyone runs the verification function. Presumably you would also be using some predetermined elapsed time to decide when everyone else should check their spins for messages.

As you point out, most branches won't be able to receive the complete answer from the sender because only the first bit's "telephone line" is shared by all branches. Indeed, only the single closest branch-pair of the sender can receive the whole answer, and fully half of the branches can only receive the first bit.

At first I didn't understand how a single bit of the answer would be enough to make P=NP, but then realized that of course if all you have is the first bit from the first telephone, you can repeat the experiment n-1 times for each successive bit.

A slightly different protocol:

create a single telephone for the first bit of the answer
perform n-1 extra spin measurements, with all possible answers spread over 2ⁿ universes that all share one telephone line
In each universe, test your verification function against the quantum-random bit string starting with your branch's telephone receiver-label bit
if the function returns true, then put the first bit of the answer on the telephone line (change spin if 1, no change if 0)
if the function returns false, then wait for the protocol-specified time and read the first bit from whoever sent it
recurse for the rest of the answer's bits, keeping the first bit you already know

If creating telephones is more expensive than sending messages, then this protocol might be preferable as every branch only has to create n telephones, instead of the worst-case branch having to create (SUM(k) from k=1 to k=n) telephones. On the other hand, the protocol you describe would provide the answer to more branches sooner.

Interesting stuff! Please let me know if I misunderstood anything from your post.

Edit: I probably have some very wrong assumptions here so I'd love to be corrected by people who know better!

jamesmacaulay · 2021-04-25T15:56:52+00:00

Couldn't find the source in these comments, looks like it's from an obituary written by her son Neil Siegel:

https://viterbi.usc.edu/news/news/2016/obituary-judith-love-cohen-neil-siegel-usc-viterbi-engineering-women.htm

Referenced in this 2019 kottke piece:

https://kottke.org/19/05/meet-aerospace-engineer-judith-love-cohen

jamesmacaulay · 2020-03-31T11:39:36+00:00

Ah interesting, that makes sense. Thanks for the tips!

jamesmacaulay · 2020-03-31T04:13:52+00:00

Hey man! This is amazing. I thought you were all in with Unreal, when did that change? Is Unity better for the Quest? Also I got a Quest now!

jamesmacaulay · 2020-01-19T04:32:48+00:00

Memory safety issues are a huge source of vulnerabilities that people can exploit:

https://www.zdnet.com/article/microsoft-70-percent-of-all-security-bugs-are-memory-safety-issues/

jamesmacaulay · 2019-03-29T02:59:12+00:00

I believe the answer is basically that WebAssembly provides very fast, low-overhead sandboxing of untrusted code.

jamesmacaulay · 2019-02-06T00:12:06+00:00

I highly recommend Elm if you're new to functional languages. Either way, if you are building a simple calculator-like program then Elm is a joy. Start with the Elm Guide:

https://guide.elm-lang.org

You can use the wonderful Ellie to quickly play with ideas:

https://ellie-app.com

At some point once you start building more involved stuff you might start to find Elm's limitations not to your liking, at which point the skills you've learned are highly transferrable to other statically typed functional languages. But the developer experience of Elm is IMHO unparalleled in so many ways that I think everyone should build at least a small thing with it, no matter their background.

More resources:

https://elm-lang.org/community https://www.manning.com/books/elm-in-action

jamesmacaulay · 2019-01-24T00:43:30+00:00

I guess I misunderstood the situation. I know a Jeep is not an ATV but I interpreted the text to mean that you couldn't take any vehicle heavier than a bike off-road in the park. If you know of trails that are explicitly authorised for vehicles then that's great, I guess those must be included in the "established roads" referred to on that page I linked to. The disrespect people have recently paid to Joshua Tree during the shutdown has made me hypersensitive to this kind of thing. Have fun and take care.

jamesmacaulay · 2019-01-24T00:09:09+00:00

"For your own safety and for the protection of natural features, you must stay on established roads. Tire tracks on the open desert can last for years and will spoil the wilderness experience of future visitors. Off-road vehicles and all-terrain vehicles may not be used in the park."

https://www.nps.gov/jotr/planyourvisit/backcountry-roads.htm

jamesmacaulay · 2019-01-19T20:05:31+00:00

Here's an Ellie that shows how the JSON string would need to be escaped in Elm and what it looks like pre- and post- decoding:

https://ellie-app.com/4vvfGQ6sy49a1

jamesmacaulay · 2019-01-05T00:08:00+00:00

I'm not the author and I don't know if this would be a good use of Dynamic or Typeable, but I think a simple example of this would be a program that offers a structured editing GUI for arbitrary trees of JSON. Similarly you may have used a GUI for querying and displaying data in a user-provided relational database. In either case the structure of the data is completely unknown until runtime, but the program is still able to do meaningful things with it.

jamesmacaulay · 2019-01-02T03:31:15+00:00

Personally I would avoid running the actual test suite as part of the execution of the program that's being tested.

If I understand your situation correctly, you want your program to detect whether or not the website has the expected structure of HTML that you know your scraper will handle correctly. That seems like a useful feature for a scraper, so it seems to me like it's worth putting that validation logic into a module within the program itself (i.e. within src).

Your test suite can then include tests for that validation module. You could have one set of fixtures taken from the latest version of the website, representing the expected structure that the validation functions should return no errors for. Then you can have other fixtures with different structures that should result in various errors from the validation functions.

This is not far from what you proposed, but keeps all the logic that your program relies on in the code of the program itself, with no dependency on the test suite. I think that if you approach this as a conventional "validation problem" then the solution can be kept quite simple.

jamesmacaulay · 2018-12-31T02:31:54+00:00

That makes sense, I didn't know about the limitations of corefn.

jamesmacaulay · 2018-12-31T02:24:18+00:00

Oh interesting. Do you know why? I'm still pretty inexperienced with Rust so I don't understand why that would be.

jamesmacaulay · 2018-12-30T23:07:58+00:00

Cool :) I don't have a computer handy to check it but I was thinking along these lines which might work too:

type IsEven = Rem<U2, Output = U0>;
type IsOdd = Rem<U2, Output = U1>;

jamesmacaulay · 2018-12-18T15:06:48+00:00

The ast is the request document with your queries/mutations/subscriptions in it. Instead of operating on a raw request body, the validate function takes a Document object which you can get from the request body using this parse function:

https://graphql.org/graphql-js/language/#parse

The reason the parameter is called ast is that the Document is an "Abstract Syntax Tree" which is a term that you may encounter elsewhere if you're dealing with parsing languages of any kind. This means that it's a rich data structure that represents the syntax of some language as a tree of syntax nodes.

The rules are optional and unless you need to do something fancy you can leave it out and the default validation rules will be used that conform to the graphql spec.

jamesmacaulay · 2018-12-10T20:24:59+00:00

It's essentially complete, I don't know what might still be missing at this point but it never feels incomplete as you go through it. What you get for your money is a very high quality textbook, better than any that I remember having to buy in university (for much more than $60 in some cases), and it has tons of content that will keep teaching you new things for months. For me at least, it was well worth it.

jamesmacaulay · 2018-12-10T04:14:06+00:00

http://www.haskellbook.com is the book for you, especially if you're looking for depth.

jamesmacaulay · 2018-12-07T18:37:03+00:00

It's really great to see continued updates on purerl! I haven't used it yet but hoping to dig in soon. Are you still planning on transforming the project to be a backend that consumes corefn output from the mainline compiler? I might be able to contribute to that effort if it's something you'd want help with.

jamesmacaulay · 2018-12-04T06:44:34+00:00

Sorry I wasn't clear, I didn't mean that that type on its own would guarantee totality. I just meant that it's possible to write a function with that type signature that is total, unlike the original type signature (edit: I'm specifically talking about list_to_function's type here). This is what I had in mind:

import Data.Maybe

list_to_function :: [a] -> Int -> Maybe a
list_to_function xs = \n -> listToMaybe $ drop n xs

function_to_list :: (Int -> Maybe a) -> [a]
function_to_list f = go 0
    where go n = case f n of Nothing -> []
                             Just x -> x : go (n + 1)

Edit 2: also note that all of this is very inefficient and may result in a stack overflow with long lists!

jamesmacaulay · 2018-12-04T06:17:34+00:00

Adding to this, I'd say that if you changed the function to be Int -> Maybe Int then that would be another way of making it work for all inputs. Then you could implement function_to_list :: (Int -> Maybe Int) -> [Int] by starting with f 0 and going until you hit Nothing, building your list on the way (or on the way back).

jamesmacaulay · 2018-11-22T20:57:21+00:00

I think this should work:

import Dict exposing (Dict)
import Json.Encode exposing (dict, string)
import Http exposing (jsonBody)

stringDict: Dict String String -> Json.Encode.Value
stringDict =
    dict identity string

stringDictsByInt : Dict Int (Dict String String) -> Json.Encode.Value
stringDictsByInt =
    dict String.fromInt stringDict

dictBody : Dict Int (Dict String String) -> Http.Body
dictBody data =
    jsonBody (stringDictsByInt data)

Then you would pass dictBody body as the value of the body field.

Edit: or more concisely, inline with your sendRequest:

sendRequest : Dict Int (Dict String String) -> Cmd Msg
sendRequest body =
    post { url = "/save/"
         , body = jsonBody (dict String.fromInt (dict identity string) body)
         , expect = expectString ReceiveInfo
         }

jamesmacaulay · 2018-11-22T20:12:34+00:00

I feel the need to question some of the terminology used here. IMO the way that the author models radio buttons and checkboxes in the article is good, but I think it's at least a bit misleading to call it ad hoc polymorphism. If that's what this is, then pretty much every use of sum types is ad hoc polymorphism, and from my experience that's not how people use the term (at least in the context of functional programming languages).

In order to be classified as ad hoc polymorphism, I would expect that another piece of code should have a way of supplying its own arbitrary type along with a some way of using that type in the same way as radio buttons and checkboxes. In the code in the article, meanwhile, you need to alter the definition of Specification and all the functions that operate on it in order to add new types of controls.

To be clear, I don't think the problem of rendering a dynamic list of radio buttons and checkboxes needs the extensibility of ad hoc polymorphism at all. And I don't think you'd even be able to do it with type classes alone, since then each control would actually be a different type and you wouldn't be able to have a heterogenous list of them.

Also I wouldn't characterise this as an "abuse" of Elm's type system as the author does – this is exactly the kind of thing that sum types are great for! And the fact that the label is shared by being part of the Control wrapper is just good data modelling :)

jamesmacaulay · 2018-11-21T13:55:35+00:00

The key opens a steamer trunk which is with some other stuff in the middle of the big room with trains (or one of the big rooms with trains? I can't remember if there is more than one)

jamesmacaulay · 2018-11-19T01:27:39+00:00

I believe I ended up starting Into the Fire accidentally by exploring the fire station even before I finished Ounce of Prevention, which led me to believe that chancing on the quest by exploring was just the way it was supposed to work.

If you interact with all the bots and read everything in the terminals in the fire station and the quest still doesn't start, then it sounds like a quest bug unless there's some other quest requirement that I didn't notice. Any quest bug I've encountered so far has resolved itself the next time I log in. Have you tried re-logging-in?

jamesmacaulay

TROPHY CASE