PDA

View Full Version : [3.x] Divinatory Alternating Turing Machines



Doc Roc
2009-11-28, 01:17 PM
They're certainly possible. Are we interested in their implications? I hold that they can satisfactorily implement the Church-Turing-Deutsch principle.

kamikasei
2009-11-28, 01:22 PM
I'm pretty sure this thread makes Cortana cosplay as a catgirl, then kills her. Don't do it, man.

Doc Roc
2009-11-28, 01:24 PM
:: sighs ::

Prepare the Trans-Catgirl engines. We're going to warp.

Radar
2009-11-28, 01:37 PM
Well, there was a thread about looped Contingency computers (http://www.giantitp.com/forums/showthread.php?t=126223) at this forum already, so why not venture another road paved with suspiciously human-sized cat ears?

jseah
2009-11-28, 04:45 PM
So use another road. That is fine.

I mentioned in the dragon thread a way to improve Divination chances by asking recursive questions.

Perhaps someone can analyse the probability and determine if this does really improve chances?

Qn1: subject matter X
yes/no
- confidence in answer = 0.9

Qn2: is qn 1 correct?
Qn3: is qn 2 correct?

Does asking more such questions improve accuracy? By how much does it improve it?

Eldan
2009-11-28, 05:27 PM
Can't we build our contingency computers with items casting contingency ever round? contingency traps, maybe?

sonofzeal
2009-11-28, 05:42 PM
So use another road. That is fine.

I mentioned in the dragon thread a way to improve Divination chances by asking recursive questions.

Perhaps someone can analyse the probability and determine if this does really improve chances?

Qn1: subject matter X
yes/no
- confidence in answer = 0.9

Qn2: is qn 1 correct?
Qn3: is qn 2 correct?

Does asking more such questions improve accuracy? By how much does it improve it?
I haven't crunched the numbers, but your accuracy is going to be strictly limited. As soon as an incorrect "no" is received, the chain is broken.

Consider the following:


Qn1: subject matter X
yes/no
- confidence in answer = 0.9

Qn2: is qn 1 correct?
Qn3: is qn 1 correct?


If you ask two questions, you have an (0.81 + 0.01) = 82% chance of them agreeing, and if both agree you have a (0.81/0.82) = 98.78% chance of that being the correct answer. In the 18% chance of disagreement, you have a 50% chance of being correct. Therefor, if you ask the question twice you have a (0.82*0.9878 + 0.18*0.5) = 90% chance of being right. This is interesting.


(summary for the non-math types: asking the same question twice does not improve your odds of knowing the right answer)


I'll work out the three-question case soon. If anyone can double check my logic, I'd appreciate it.

jseah
2009-11-28, 05:48 PM
No, no what I meant was that each qn asks if the previous qn was correct. Not if the first one was.

The spell prevents asking the same qn anyway, hence the need to ask if the previous qn was correct. Asking about the 1st qn twice does nothing.

Myrmex
2009-11-28, 05:50 PM
So use another road. That is fine.

I mentioned in the dragon thread a way to improve Divination chances by asking recursive questions.

Perhaps someone can analyse the probability and determine if this does really improve chances?

Qn1: subject matter X
yes/no
- confidence in answer = 0.9

Qn2: is qn 1 correct?
Qn3: is qn 2 correct?

Does asking more such questions improve accuracy? By how much does it improve it?

I thought further divinations on the same subject revealed the same results. Maybe there's some super-mega divination out there.

sonofzeal
2009-11-28, 05:54 PM
For three questions..

Pascal's Triangle gives us the following....

Number of ways to get three right = 1
Number of ways to get two right = 3
Number of ways to get one right = 3
Number of ways to get zero right = 1


Odds of getting that arrangement...

Three right: 0.9^3 = 0.729
Two right: 3 * (0.1 * 0.9^2) = 0.243
One right: 3 * (0.9 * 0.1^2) = 0.027
Zero right: 0.1^3 = 0.001


Our actual return cases

All three agree: (0.729 + 0.001) = 0.73
Reliability when that happens: (0.729 / 0.73) = 0.99863

Two out of three agree: (0.243 + 0.027) = 0.27
Reliability when that happens: (0.243 / 0.27) = 0.9


Our total confidence

(0.73 * 0.99863 + 0.27 * 0.9) = 0.972


.....so asking the same question three times does boost our confidence, though not nearly as high as one might suspect. Go figure.

sonofzeal
2009-11-28, 06:05 PM
No, no what I meant was that each qn asks if the previous qn was correct. Not if the first one was.

The spell prevents asking the same qn anyway, hence the need to ask if the previous qn was correct. Asking about the 1st qn twice does nothing.
Doesn't work. I addressed that in the first two sentences. The rest was my alternative (although you're right that you can't ask the same question twice).

The issue I have with your approach is that it switches polarity too much. In an arbitrarily long sequence of questions, everything is going to approach a 8:2 ratio of "yes" to "no", with the "no"s coming in pairs or separated by one or two "yes"s. The first couple will give you some valuable information, but the end result of the system is the same regardless of the initial question.

jseah
2009-11-28, 06:42 PM
Ok, I have some time, so I'll take a crack at it.

The problem isn't whether you will get a yes answer or not.
If you do a raw probability calculation:
qn-------answer
X-------C 0.9----IC 0.1
1-------Y 0.82---N 0.18
2-------Y 0.756--N 0.244
n
Y Pn-1(Y)*0.9 + Pn-1(N)*0.1
N Pn-1(Y)*0.1 + Pn-1(N)*0.9

Which averages to 50-50 at N approaching infinity.


The problem is in the chain of yeses and noes.
You know the chain that comes out. That's your answer from the spell.
Given a series of Ys and Ns, what is the probability that the first one is correct?
Let's say we do this 10 times:
X--1--2--3--4--5--6--7--8--9
Y--Y--Y--Y--Y--N-N--Y--Y--Y

How many errors do we think we have?

Looks like 1 error. Number 5 is wrong.
Because when you get a wrong answer, the chain reflects it.

Let's say number 1 is wrong. The answer to the original qn was false.
Then number 2 must also be wrong and 3 and 4 as well.
Number 5 then becomes correct and 6/7/8/9 are wrong.
So only 5 is correct.

Let's say number 2 is wrong. The answer to 1 must be wrong. Thus number 1 should be N. Thus the original qn was false. The thing propagates back through the chain and you have the same scenario.
Again, only 5 is correct.

So when there's only 1 error, we have a situation where either:
only 5 is in error
all but 5 are in error

The odds are overwhelmingly likely that only qn5 is in error.
Note that this applies even if the X, the qn we're concerned about, is answered wrongly.

Opposite situations:
No errors: P = 0.349
X--1--2--3--4--5--6--7--8--9
Y--Y--Y--Y--Y--Y-Y--Y--Y--Y
All errors: P = 10^-10
X--1--2--3--4--5--6--7--8--9
N--Y--Y--Y--Y--Y-Y--Y--Y--Y

1 error: P = 0.387
X--1--2--3--4--5--6--7--8--9
Y--Y--Y--Y--Y--N-N--Y--Y--Y
9 errors: P = 9 x 10^-9
X--1--2--3--4--5--6--7--8--9
N--Y--Y--Y--Y--N-N--Y--Y--Y

2 errors: P = 0.194
8 errors: P = 3.645 x 10^-7
X--1--2--3--4--5--6--7--8--9
Y--Y--N--N--Y--N-N--Y--Y--Y
OR
X--1--2--3--4--5--6--7--8--9
Y--Y--Y--Y--Y--N-Y--N--Y--Y

3 errors: P = 0.0574
7 errors: P = 8.75 x 10^-6
X--1--2--3--4--5--6--7--8--9
Y--Y--N--N--Y--N-N--Y--N--N
OR
X--1--2--3--4--5--6--7--8--9
Y--Y--N--N--Y--N-Y--N--Y--Y
OR
X--1--2--3--4--5--6--7--8--9
Y--Y--Y--Y--N--Y-Y--N--Y--Y

4 errors: P = 0.0111
6 errors: P = 0.000138

5 errors: P = 0.00149

Assuming that we take the higher probability one, and that we can tell the positions of the error if there are three or less (so we know if our answer was right)

We have a confidence of:
P(0 + 1 + 2 + 3) - P (10 + 9 + 8 + 7)
= 0.987

or close to 98.7% confidence. An improvement.

----------------------------------------------------------------------------------------

sonofzeal:
I agree that making more questions have a diminishing return.

Adding more questions to the chain allows you to "resolve" more errors because you can see them clearer.

The improvement quickly gets into the small percentages of 99.9% which is not worth the spell.

Still, to go from 1 in 10 error to 1 in 100 error by using 10 questions instead of 1 allows you to bypass the "no asking again" rule.

sonofzeal
2009-11-28, 07:24 PM
sonofzeal:
I agree that making more questions have a diminishing return.

Adding more questions to the chain allows you to "resolve" more errors because you can see them clearer.

The improvement quickly gets into the small percentages of 99.9% which is not worth the spell.

Still, to go from 1 in 10 error to 1 in 100 error by using 10 questions instead of 1 allows you to bypass the "no asking again" rule.
Yes, it occurred to me after you posted that a devoted questioner (and we're probably dealing with one) could count back the number of required errors for each interpretation. Still, that becomes a difficult measure to implement for long sequences, one that will eventually tax even the most agile brain with its double and triple and umptuple negations. Its confidence will also always be less than or equal to the confidence obtained through repeated askings of the same question. I'm beginning to suspect that the two might actually be equal, but the implementation is certainly easier if you can get N different casters to all cast Divination for the same question. All you have to do is tally "yes" and "no" and go with the greater one, rather than follow a series of mental gymnastics.

jseah
2009-11-28, 07:41 PM
Still, that becomes a difficult measure to implement for long sequences...
<...>
All you have to do is tally "yes" and "no" and go with the greater one, rather than follow a series of mental gymnastics.
I suddenly get the hilarious image where you have a whole bunch of automated question-asking constructs who print out a series of Y/Ns below a target question on a piece of paper. Like a oracle who outputs answers in a string of paper with hole/no hole. XD

And a whole office dedicated to working out the confidence level of the result. People flicking abacuses going "20C5 x 0.9^15 x 0.1^5 = ..."

And another office dividing the problem set into yes/no halves and collating the reams of processed data, plotting it onto a giant sand table.
Sifting out suprious data points and interpreting a dynamic map.

Then finally passing it to the King's military generals who spent a million gp to get the real-time geographical data about troop movements.

sonofzeal
2009-11-28, 07:55 PM
I suddenly get the hilarious image where you have a whole bunch of automated question-asking constructs who print out a series of Y/Ns below a target question on a piece of paper. Like a oracle who outputs answers in a string of paper with hole/no hole. XD

And a whole office dedicated to working out the confidence level of the result. People flicking abacuses going "20C5 x 0.9^15 x 0.1^5 = ..."

And another office dividing the problem set into yes/no halves and collating the reams of processed data, plotting it onto a giant sand table.
Sifting out suprious data points and interpreting a dynamic map.

Then finally passing it to the King's military generals who spent a million gp to get the real-time geographical data about troop movements.
Well, you don't really need to know the confidence level of the result, or rather you only need to work it out once for each number of questions asked.
But yes, amusing. =P

jseah
2009-11-28, 07:58 PM
I did the confidence level wrong.

The 4 error one is still 100 times more likely that the reverse 6 error explanation.

Let's say we get 1 error, given that we have 1 error or 9 errors...
The chances of having 1 error instead of 9 is 43 million times more likely.

At the 4 error scenario, given that we have 4 errors or 6 errors...
We are 81 times more likely to get 4 errors than 6 errors (1.22% chance of 6 errors)

At the 5 error scenario, we are at 50-50, no info gained. Confidence in original question is back to 90%.


So what we did was ask and hope that the thing doesn't give too many errors. Coz each error lowers our accuracy back towards 90%.

Luckily the chances of getting a 4 error is 1.11% and a 5 error is 0.1%.
And if it does happen, tack on another 10 questions and the distribution should go back to normal and you can extract your answer again anyway.

sonofzeal
2009-11-28, 08:34 PM
At the 5 error scenario, we are at 50-50, no info gained. Confidence in original question is back to 90%.
Are you not including the original question in your calculations? I was assuming it counted for one of your errors or not, which would only make sense. In that case, the 5 error scenario still leaves you at 50-50, and it would be a fallacy to assume the original question with 90% odds.

In general, an odd number of Divinations is going to be superior to an even number. Ties really mess up your confidence.

Tokiko Mima
2009-11-29, 02:49 AM
A device that does this would be the size of a small city and take in the neighborhood of 7.5 million years to answer the really difficult questions. However, I'll save you some time reading ahead and tell you that the correct answer is 42. :smalltongue:

jseah
2009-11-29, 04:20 AM
Are you not including the original question in your calculations? I was assuming it counted for one of your errors or not, which would only make sense. In that case, the 5 error scenario still leaves you at 50-50, and it would be a fallacy to assume the original question with 90% odds.

In general, an odd number of Divinations is going to be superior to an even number. Ties really mess up your confidence.
My apologies. I seem to be forgetting my statistics. Yes, 50-50 is screwy.
And yes, it includes the original qn.

It's a good point. Perhaps we'll use 9 question instead of 10.

sonofzeal
2009-11-29, 09:47 AM
Case for four questions (including the original question)


Pascal's Triangle gives us the following....

Number of ways to get four right = 1
Number of ways to get three right = 4
Number of ways to get two right = 6
Number of ways to get one right = 4
Number of ways to get zero right = 1



Odds of getting that arrangement...

Four right: 0.9^4 = 0.6561
Three right: 4 * (0.1 * 0.9^3) = 0.2916
Two right: 6 * (0.1^2 * 0.9^2) = 0.0486
One right: 4 * (0.9 * 0.1^3) = 0.0036
Zero right: 0.1^4 = 0.0001


Our actual return cases....

All three agree: (0.6561 + 0.0001) = 0.6562
Reliability when that happens: (0.6561 / 0.6562) = 0.9998

One different: (0.2916 + 0.0036) = 0.2952
Reliability when that happens: (0.2956 / 0.0036) = 0.9878

Two different: (0.0486) = 0.0486
Reliability when that happens: 0.5


Our total confidence
(0.6562 * 0.9998 + 0.2952 * 0.9878 + 0.0486 * 0.5) = 0.972



.....from this we can hypothesize that accuracy jumps at every odd number, but remains the same at the following number. So C(10) = C(9) > C(8). Someone could test this if they wanted.

And until I see other evidence, I'm going to assume that jseah's algorithm provides identical confidences. At very worst, these results would provide the upper bound.

Doc Roc
2009-11-30, 03:22 PM
If I could provide you with an error-free divination mechanism with full repeatability, would that help? The issue is that it's deeply constrained in what it can discuss, basically boiling down to yes/no answers to one or two very specific kinds of questions. I'm wondering if that's enough to be a turing oracle.

BooNL
2009-11-30, 03:40 PM
*has just gotten a headache*

sonofzeal
2009-11-30, 03:45 PM
If I could provide you with an error-free divination mechanism with full repeatability, would that help? The issue is that it's deeply constrained in what it can discuss, basically boiling down to yes/no answers to one or two very specific kinds of questions. I'm wondering if that's enough to be a turing oracle.
Please, elaborate! I'd love to hear how this works!

Keld Denar
2009-11-30, 04:08 PM
Ask questions with 100% reliable answers. (http://www.d20srd.org/srd/spells/commune.htm)

Sure, you have to burn 100 XP every time, but thats worth it for 100% reliable answers for up to CL questions per casting.

sonofzeal
2009-11-30, 04:12 PM
Ask questions with 100% reliable answers. (http://www.d20srd.org/srd/spells/commune.htm)

Sure, you have to burn 100 XP every time, but thats worth it for 100% reliable answers for up to CL questions per casting.
Aware of it. Not any more reliable than the being you manage to contact. Contacting Boccob or Vecna (if you can do so safely) are safe bets, but you may just wind up on the line with a minion or somesuch. At least with Divination, you know your odds.

Keld Denar
2009-11-30, 04:14 PM
Vecna finds your lack of faith disturbing...

sonofzeal
2009-11-30, 04:21 PM
Vecna finds your lack of faith disturbing...
Ia Ia Erythnul Fharlanghn!

Kalirren
2009-11-30, 04:30 PM
I suddenly get the hilarious image where you have a whole bunch of automated question-asking constructs who print out a series of Y/Ns below a target question on a piece of paper. Like a oracle who outputs answers in a string of paper with hole/no hole. XD

And a whole office dedicated to working out the confidence level of the result. People flicking abacuses going "20C5 x 0.9^15 x 0.1^5 = ..."

And another office dividing the problem set into yes/no halves and collating the reams of processed data, plotting it onto a giant sand table.
Sifting out suprious data points and interpreting a dynamic map.

Then finally passing it to the King's military generals who spent a million gp to get the real-time geographical data about troop movements.

In my Eberron game, my PC eventually became the head of New-Cyran Intellgence. She actually built an epic-ly expensive super-Divinatory eldritch machine to do just this.

Ah, the possibilities that open when you have a significant fraction of the taxes of an entire nation's GDP at your disposal...every year...

Doc Roc
2009-11-30, 10:22 PM
Actually, the trick is very simple. My idea of simple and yours will differ.
Optional but recommended:

Learn the Modron language.
Modron is canonically mathematical in nature and precise, lacking any ambiguity, meaning that it is in fact executable....
Or at least that a large and meaningful subset of it can be discussed within ZF-set theory.
Write out, on paper, a basic operating system, probably a Forth, hopefully Modron.
Use dominate person on yourself.
Instruct yourself to follow the instructions on your sheet of paper.
Load yourself with the operating system as your instructions.

You now have an onboard computer that runs at the speed of thought.
Hilariously enough, this is infinitely fast in D&D, as thinking is faster-than-free.
Worship a deity who includes time in their portfolio. Ideally, start a cult to a deity with computability in their portfolio. I recommend St. Turing.
Buy phylactery of faithfulness.

Now, would one say that falling into an infinite loop would adversely affect one's standing with your deity? You certainly wouldn't be able to pray anymore, and if you are neutral good, say, it'd certainly put you in a position to become lawful neutral.....

:smallredface:

Jack_Simth
2009-11-30, 10:57 PM
I haven't crunched the numbers, but your accuracy is going to be strictly limited. As soon as an incorrect "no" is received, the chain is broken.

Consider the following:


Qn1: subject matter X
yes/no
- confidence in answer = 0.9

Qn2: is qn 1 correct?
Qn3: is qn 1 correct?


If you ask two questions, you have an (0.81 + 0.01) = 82% chance of them agreeing, and if both agree you have a (0.81/0.82) = 98.78% chance of that being the correct answer. In the 18% chance of disagreement, you have a 50% chance of being correct. Therefor, if you ask the question twice you have a (0.82*0.9878 + 0.18*0.5) = 90% chance of being right. This is interesting.


(summary for the non-math types: asking the same question twice does not improve your odds of knowing the right answer)
You've got a false assumption: We're worried about the overall accuracy. That's not the case. What we're worried about is determining whether we need to seek the answer elsewhere, or be satisfied with the results of the divination.

Start with a divination that's correct 90% of the time, and incorrect 10% of the time.

If both the main question, and the first meta-question are in agreement, then we've got the 98.75% chance of having the right answer. Which is good. If they're not in agreement (18% of the time), then we look for an alternative source for answering our question, and don't care what the results of the divinations were.

Yes, we'll occasionally be stopping for additional verification when the original question gave us the correct answer, but we now have procedure which gives us a correct answer 81% of the time, an uncertain result 18% of the time, and an incorrect answer 1% of the time - starting from a divination that gives us a correct answer 90% of the time, and an incorrect answer 10% of the time. We now have some "wrong answer" insulation, at a cost of how often we get the "right answer". If you ask similar meta-questions a few more times, there's some tricks you can do to get the answer more reliably (at a 9:1 right:wrong ratio on the base divination, being able to trick the DM into thinking you're not asking the same question repeatedly crashes the probability of a wrong answer to zero pretty fast, simply by way of majority vote).

But it's a moot point (in D&D, at least) - you're making repeated divinations on the same subject - which is supposed to use the same result for each answer after the first.

sonofzeal
2009-11-30, 11:08 PM
You've got a false assumption: We're worried about the overall accuracy. That's not the case. What we're worried about is determining whether we need to seek the answer elsewhere, or be satisfied with the results of the divination.

Start with a divination that's correct 90% of the time, and incorrect 10% of the time.

If both the main question, and the first meta-question are in agreement, then we've got the 98.75% chance of having the right answer. Which is good. If they're not in agreement (18% of the time), then we look for an alternative source for answering our question, and don't care what the results of the divinations were.

Yes, we'll occasionally be stopping for additional verification when the original question gave us the correct answer, but we now have procedure which gives us a correct answer 81% of the time, an uncertain result 18% of the time, and an incorrect answer 1% of the time - starting from a divination that gives us a correct answer 90% of the time, and an incorrect answer 10% of the time. We now have some "wrong answer" insulation, at a cost of how often we get the "right answer". If you ask similar meta-questions a few more times, there's some tricks you can do to get the answer more reliably (at a 9:1 right:wrong ratio on the base divination, being able to trick the DM into thinking you're not asking the same question repeatedly crashes the probability of a wrong answer to zero pretty fast, simply by way of majority vote).

But it's a moot point (in D&D, at least) - you're making repeated divinations on the same subject - which is supposed to use the same result for each answer after the first.
As previously noted, you can (probably; it hasn't been proven yet) get the same result by asking "was the answer to my last question correct", which is technically a different question with a different % roll. YMMV.


As to the rest, the question is whether or not to try for the second casting at all. The point is that if you're sitting at one, you don't really have much to gain by casting it a second time unless you're shooting for three. The one you have could be wrong... but your verifier is just as likely to be wrong, and if either of them are wrong you're in trouble. Shooting for three gives you that extra piece of information you asked about anyway.

Doc Roc
2009-11-30, 11:22 PM
The trans-catgirl engine (http://docs.google.com/File?id=dg678bn3_160hrbvpvgh_b) is capable of navigating the terrifying phase-space between worlds.

jseah
2009-12-01, 07:13 AM
The trans-catgirl engine (http://docs.google.com/File?id=dg678bn3_160hrbvpvgh_b) is capable of navigating the terrifying phase-space between worlds.
That is hilarious. XD Thanks, that just made my day.


As previously noted, you can (probably; it hasn't been proven yet) get the same result by asking "was the answer to my last question correct", which is technically a different question with a different % roll. YMMV..
Actually, it's the same. I think.

Note that in my analysis, it boiled down to opposing results.
Either you know you have 1 error or 9 errors. 3 errors or 7 errors.

This situation is exactly the same as the 1 disagreeing vs 9 agreeing that you would get from 10 people asking the same question.
Either that 1 guy is wrong or the 9 guys are wrong.

So yes, they have the same probability. There's probably some kind of mathematical law that prevents you from extracting more than a certain amount of information from unreliable sources.

I like the chained questions one better though. Not least because I came up with it. XD EDIT: well, refined it from another idea. It wasn't 100% original.
Still, you have to admit that requiring more people means higher risk.