Wigner's Fuckbuddy Is A Superposition of Top And Bottom
- The title of this article is not correct because of technical limitations. The correct title is actually Wigner's Fuckbuddy Is A (|Top⟩ + |Bottom⟩)/√2.
Wigner's Fuckbuddy Is A (|Top⟩ + |Bottom⟩)/√2 is a Brainfuck derivative created by User:Quintopia in 2013, who, until that time, had managed to make it for seven years in the esolang community without creating a BF derivative. Fortunately, his first such language is unimplementable via current technology and, hopefully, by any technology ever. It is likely possible to simulate a proper implementation, however, with no guarantees as to the running time of any program. It assumes the reality of a quantum theory to which applies Everett's Theory of the Universal Wavefunction (the Many-Worlds Interpretation).
Differences from Brainfuck
The language is identical to (an unbounded non-wrapping implementation of) Brainfuck, except for the following changes:
- When no user input is available, the , operator does not block, but instead reads in a random arbitrary-precision number and maintains a list of numbers thus generated.
- Rather than output immediately, any cell that would be output by . is placed in a queue until the program halts.
- Upon program halt, if the output queue contains n numbers while the list of random inputs contains less than n, the interpreter reads in enough random numbers to ensure that the list of such numbers is at least as long as the output queue. If the first n numbers in the random input list match the contents of the output queue, the output queue is outputted. If any numbers do not match, nothing is outputted and most or all of the amplitude assigned to the current world's part of the universal wavefunction will be shifted toward the world in which the random numbers which were read in are equal to those which would have been outputted in this world.
Implementation Notes
- It is up to the implementer to decide how long the random numbers which are read in are, and what distribution they are drawn from. However, it is highly recommended that the source of randomness be a true source and not a PRNG, and that it have a remote point of origin. Using the noise in the CMBR would be ideal. Using more local sources of randomness, such as user mouse motion and hard drive access times, is HIGHLY DISCOURAGED.
- User input should be parsed in the following way: If the next byte is a digit ([0-9]), greedily read in as many digits as possible, treat them as one decimal number, and store it in the current cell. Otherwise, read a single character into the current cell.
- It is considered not only polite, but simply good business practice to warn the user that their portion of the multiverse is about to be mangled out of existence before performing the amplitude shift at the halt of a non-matching program execution.
Computational Time Complexity
This language is obviously Turing-complete. What is more interesting is that hard problems can be solved more quickly. In particular, all problems in NP can be solved in polynomial time using a Wigner's Fuckbuddy Is A (|Top⟩ + |Bottom⟩)/√2 program. The language is one way of implementing a Non-deterministic Turing Machine with the added implementation detail that if more than one accepting branch of the evaluation tree exists, one is chosen at random proportional to the number of non-accepting branches which share part of its evaluation path. As such, if a problem has multiple solutions, it may be possible to generate all of them by running the program which solves the problem repeatedly. Of course, if a programmer does a poor job, it is also possible that a program may fail to generate any solution even when one exists. It is useful for the programmer to think of a program as a transition function which explores the space of inputs/outputs in the fashion of a Markov chain or an attractor. If the programmer does not create a program that moves amplitude from all possible worlds into the subset of worlds which generate correct solutions, then they may find they are one of the worlds which they didn't force to converge on a solution and get, as a result, no solution at all.
Scott Aaronson calls this paradigm of computation "Anthropic Computing" after the Anthropic Principle of cosmology, and says that in addition to solving all problems in NP, it can actually solve all problems in a larger class called BPPpath.
Examples
To be continued...
References
- NP-Complete Problems and Physical Reality by Scott Aaronson