If you're weirded out by the nondeterminism, you might want to look at deterministic vs. nondeterministic finite state machines, they're a bit simpler.
> Nondeterministic Turing machines are defined in the same way as their deterministic counterparts, except that instead of a transition function associating one and only one $(p,\tau,d)$ to each $(state, symbol)$ pair $(q, \sigma)$, there is a transition relation (which we will again denote by $\Updelta$) consisting of any number of ordered 5-tuples $(q,\sigma,p,\tau,d)$.
1. What difference does that make? 2. Why would that make it nondeterministic 3. What difference will having a transition function have in relation to a transition relation?
Okay, let everything about an initial state be $x_i$ and everything that the machine can do in one step be $y_i$.
In a deterministic TM, given $x_i$, there is a definite $y_i$ given by the transition function.
In an NTM, you have a relation, i.e. a set of pairs $(x_i, y_j)$. Given $x_i$, you are allowed to transition to all $y_j$ such that $(x_i, y_j)$ in a pair in the relation.
What does it mean to transition to more than one thing? Well, you can't implement that on a physical Turing machine. You can think about it a few ways:
- a number of "ghost copies" of the TM split off. each of them does one of the possible things.
- the TM rolls a die to pick which transition to do.
The latter is why we call it 'nondeterministic'. But I think imagining the first is a bit easier.
The important point is that an NTM is the same as a TM that "already knows how to get to the answer". For example, if the question is "does this maze have a solution", the TM can always take the right path. The NTM can take all paths.
So if you want to talk about P vs. NP you'll talk about NTMs.
No, that's a totally different thing. Quantum superposition is a lot more restrictive than this NTM "taking all paths at once" thing.
NTMs work if any of the paths work. A quantum computer's wavefunction must have every path in it, and you have to figure out a clever algorithm to make all the wrong paths destructively interfere.
So quantum computers have little to do with the P vs. NP problem.
But when my Dad went back for his Ph.D. I got to help him with his homework. He'd reduced a problem to an integral he didn't recognize. It was the complementary error function.
I need something that's 1 near $0$, then smoothly transitions to a decaying function so that the whole thing has area 1 and never goes negative
I'm certain it should be a smooth plateau function near the origin summed with some lopsided distribution with support $[\epsilon,\infty)$, $\epsilon>0$.
Now if only I hadn't change my mind about how to write it about three times I might have had a consistent notation at the beginning. SHould be right now.
I need a smooth ramp function to multiply my Gaussian with
Not sure if I need ACM, this seems quite reasonable.
@dmckee If you multiply a Gaussian with a smooth $0\to 1$ ramp function, you should get a "ramped" Gaussian, and since it's $\le$ everywhere to the original one, it's $L^1$ integrable.
Then take the plateau, integrate it along its support in $[0,\infty)$, call that $\epsilon<1$.
Then normalize the ramped Gaussian to $1-\epsilon$
Slide it over so that the end of its support on the left just touches that of the plateau
