Is it possible to write a program that can solve a problem the programmer can't?

Is it possible to write a program that can solve a problem the programmer can't?

Other urls found in this thread:

en.wikipedia.org/wiki/Bayes'_rule
en.wikipedia.org/wiki/Monty_Hall_problem
twitter.com/NSFWRedditImage

Yes

Count the number of rows in a very long document

A programmer CAN solve that, it just takes the programmer more time than it does for the computer program.

Stand back Dyson

50%

50% is the most common /obvious answer. That the question is being asked at all should suggest to you it's not correct. Which it is not.

2/3

Not if it's 20 billion lines long. Which could be just a few hundred gigabytes.

That's an extremely autistic thing to think, I'd never even considered the lifespan of the programmer. I'm actually impressed, that's a very correct and sterile way to think about the matter.

Probabilities are an illusion

The situation presented is that you have taken one gold ball, so as seen in the image.
If you now take the second one from the same box, it's either going to be gold, or silver. That depends on which box you are in.
I can see where the 2/3 opinion comes from, but that would imply that you could also take from the other boxes, which you can't.

Does the programmer have infinite time? If so, no. Humans are Turing complete and can do any program a computer can given infinite time and resources.

Given reasonable human restrictions? No fucking shit. For example, I am not going to manually calculate millions of solutions to different gravitational fields but a computer can spit out those results in seconds.

en.wikipedia.org/wiki/Bayes'_rule

You're mistaken.

yes.
modern AIs are already better than people in some tasks

Isn't that why you write computer programs in the first place?

So either you pick the GG or GS box to get a gold to begin with
If you picked the GG box it's 100%
If you picked the GS box it's 0%
So since you have a 50% chance of having picked the either box, it's now 50% because you have to have picked GG

You're more likely to have picked the GG box than the GS box though.

Why, if you can't look into the boxes?
Two boxes (third one is already ruled out) and closed. They look exactly the same fromt he outside. Choose one by random. You have the same chance to pick either GG or GS.

Yeah but consider the probability of picking a gold ball in the first place. You've got a 1/3 chance overall of picking a gold ball from the first all-gold bin, and only a 1/3 * 1/2 = 1/6 chance of picking the gold ball from the middle bin. Therefore, if the first ball you pick is gold, you're actually more likely to have selected the first bin than the middle bin, and this additional information means you've actually got a 1/3 / (1/2) = 2/3 chance of having selected the all-gold bin.

For a more extreme example, imagine there are only two bins, each with 100 balls. Bin 1 has 99 gray balls and 1 gold ball, and bin 2 has 100 gold balls. Intuitively, if you randomly take a ball from a bin, and it happens to be gold, you know that you're more likely to have selected it from bin 2 than bin 1. This question is the same scenario, but with much smaller numbers, making it less obvious.

It's not opinion, it's mathematical fact.

Mind = blown.

>Yeah but consider the probability of picking a gold ball in the first place.
How does that even matter if you have already picked it in the past? The probability of picking a gold ball in the first place is 100%.
You do not have a magical hand that can only pick gold balls (in this case it would be more attracted to the GG one). The presented case is a single-time scenario where you have chosen at random and it just so happens to be a gold one. It could have been silver as well, the boxes look the same from the outside after all. Maybe that happens on another draw, but in this presented case, it already happened and it's not guaranteed to happen again. Therefore you can discard all the information of what happened in the past. Now you only have 2 boxes and you have a gold ball in your hand, the next draw will depend on which box it is, which has the same chance for all boxes, 50/50

It's 1/3d since there is only one box with two gold balls.

>How does that even matter if you have already picked it in the past?
The laws of probability are impartial to matters of past and future. All that matters is whether you know the outcome or not. In this case, you know that you got a gold ball, but you don't know which bin you originally selected. As a result, you're more likely to have picked the GG box.

The specific principle at work here is called conditional probability (google it). The overall probability of picking a gold ball first is 1/3 + 1/6 = 1/2 by Bayes law, and the probability of it picking it specifically from the first box is 1/3, so you get 1/3 / (1/2) as the probabilty of having picked the GG box, provided that you picked a gold ball first.

Probability is not an inherently intuitive discipline, unfortunately. You can't just feel it out.

This user is right, but could also be because the scenario was poorly written.
It states you already picked a ball and it was gold, and that's the current state. How this was written makes me assume it only takes into account the probabilities from here on out. So the SS box is already discarded, and this box can only be GS or GG, so 50%.

p=np
solve pls

>This user is right, but could also be because the scenario was poorly written.
No, it's not the scenario, it's your brains.
>this box can only be GS or GG, so 50%.
You're making a critical mistake here by assuming that it's exactly 50%. You can't just make up values arbitrarily like that.

Here's the original problem that this question is based on:
en.wikipedia.org/wiki/Monty_Hall_problem

>I have never studied turing completeness: the post

How would you go about making a simulation then?
Step 1: Choose one box at random, each with the same chance
Step 2: If Silver, discard the whole experiment, since it is not the presented case
^ The above would already distort the result, because then you'd have the magic hand that could only pick gold balls and would be more attracted to the GG box, since GS has a 50/50% of discarding simulation and thus giving it only half the chance to appear, while GG has a 0% chance.

If you instead start checking the chance straight from the beginning, then it is 1/3, because only one out of 3 boxes can be the correct one and they have the same chance. What happens after that does not change the content of the box you chose.

P=0 or N=1

A simulation with 500 trials gives me about 2/3 as the answer every single time. Here's the code (it's python 2).

import copy
import random

startBoxes = [['G','G'],['G','S'],['S','S']]

# pick a ball
def pickBox(boxes):
idx = random.randint(0,len(boxes) - 1)
return boxes[idx]

# pick a ball from the given box and delete it
def pickBall(box):
idx = random.randint(0,len(box) - 1)
res = box[idx]
del box[idx]
return res

# the number of times a gold ball is picked first
goldFirst = 0
# the number of times a gold ball is picked the second time, after already picking a gold ball the first time
goldSecond = 0

def doTrial(num):
global goldFirst
global goldSecond
print "Trial #" + str(num)
boxes = copy.deepcopy(startBoxes)
box = pickBox(boxes)
ball1 = pickBall(box)
if ball1 == 'G':
print "Picked a gold ball first"
goldFirst += 1
ball2 = pickBall(box)
if ball2 == 'G':
print "Also picked a gold ball second"
goldSecond += 1
else:
print "Did not pick a gold ball"

numTrials = 500
def main():
for i in range(0,numTrials):
doTrial(i)
print "Final Statistics"
print "Number of times gold ball picked first: " + str(goldFirst) + " (%" + str(100 * goldFirst / numTrials) + ")"
print "Number of times two gold balls picked: " + str(goldSecond) + " (%" + str(100 * goldSecond / numTrials) + ")"
print "Probability of picking a second gold ball after picking a first: %" + str(100 * goldSecond / goldFirst)

Do you have a problem where you know some of the possible input and output values of function f but not how function f is implemented? That's what machine learning is good at.

You only had a 50% chance of picking the gold ball if you chose the GS box, but a 100% chance of drawing a gold ball from the GG box.

A man, a wolf, and a goat all on one side of the river have access to 3 boxes with gold balls in them and are dicking about shoving their hands/paws/hooves into them, while on the other side of the river is a house with 3 lights connected to 3 switches not in the same room. How can you determine which gold ball which animal/person will hurl at each switch from across the river?

>Can't get across the river with the goat who wants to throw a gold ball at a light switch because he will be eaten by the wolf who is too busy trying to also get across the river to throw a silver ball at a switch

>Electrician troll-truck explodes in the distance because the same faggot who wired up this house to not let any pipes/electricity touch each other and also have 3 switches in the same room of their lights because underground works in 2D also wired up his car that way

>Wolf makes it halfway across the river with a silver ball and then starts crying because the goat didn't even taste that good and the only other food (the cabbage) is back on the other side of the river

>electrician drives up to pick up cabbage but brakes aren't wired properly so the truck drives into the water making a perfect bridge upon which the man walks across and slaps the shit out of the wolf and goat who are hurling silver and gold balls at light switches that were wired improperly

>House becomes a gameshow contestant offering a prize behind 3 doors. Opens 1 of its doors for the goat, wolf, man etc who enter and simply stand there and continue being slapped and also crying. House offers to let them switch the other door.

>They decline and "stick" with the third door which opens to show the dead electrician and a chest full of gold and silver balls and cabbages. Goat immediately throws up and says "op is a faggot"

This is meaningless since the requirement for the problem is picking up a gold ball first.
There is only 2 boxes with gold balls
One has two of them the other has one
So you either pick another gold or not
50%

You calculated the chance of pulling two gold balls and infinite retries if you didn't pick a gold ball first. The scenario asks the chance of pulling a gold ball when you can only choose between a box with either a gold ball or silverball.

Goddamn you're stupid

There's no difference between what you're saying.

In his scenario he tossed out the cases where he drew a silver first. That's no different from starting with drawing a gold.

Fuck you, OP.

I remeber having endless discussions about this pic on /sci/.

Having a background in statistics:
The answer is 2/3.

Why?
Because there's three possible elementary events:
-picking goldball nr. 1
-picking goldball nr. 2
-picking goldball nr. 3

Yes, from a statistical point of view there's a difference wether you grab the first or second gold ball form the first box. The reson is that there is 6 elementary events, since there are are 6 balls, no matter how they are partitioned.

No, I won't discuss that any further. Fuck you if you don't believe me.


Now to your question:
Of course! Can you see the differnce between the RGB colors "AACC10" and "AACC11"? A simple MS Paint clone can display the result.

There are not there elementary events, and it doesn't matter which gold ball you pick from the first box because you're reaching back into the same box
It's 50%

Of course. Someone who doesn't understand the Monty Hall problem can model it and figure out the probability after many repeated trials.

It's the phrasing. The third box is never a consideration, the base case is 2 boxes, hence 50%.

This is the fucking Monty Hall problem. 2/3 only if you switch boxes...lol

Actually it's the opposite.

This guy maths

Halteproblem
a program A can easily determine wether a given program B will terminate in finite steps
a programmer will have trouble with that and call me a faggot for lying on a chinese checker board

This is very simple. Right from the start we know that we didn't pick SS, so we can immediately forget that it ever existed. Either we picked GG, or GS. There is a one in two chance that we picked GG and therefore have another gold ball available.

wrong

But you already got a gold ball, so the box has to be one of the two that have at least one gold ball.

Yes, very much so. Neural nets are a prime example of this. How would you create an algorithm that takes an image and returns a string detailing what is found in that image? No programmer can solve that for images of a certain complexity. I'd certainly love to see you try, and I'd also love to see you solve the problem of doing it more efficiently than a neural net.

This isn't a monty hall situation though. There are two boxes with gold balls in them. One contains a silver ball. In either case, you have removed one. There is one ball remaining in either potential box. One is silver, one is gold. 50 % of the possible boxes contain a golden ball.

Monty hall relies on the fact that you are initially more likely to pick an unfavorable outcome, and as such, switching is more likely to garner you a win.

It's ironic that the Monty Hall problem proves you wrong and explains exactly where the 50% comes from.

It's 75%.

If you are in the box with two golden balls, there's 100% chance that the second ball will be golden.

But if you're in the box with one silver ball, there's 50% chance that you'll pick up the same golden ball again.

Thus (100+50)/2

You're assuming that one would put the ball back into the box. At no point is this mentioned.

why did you put the gold ball back in the box

A program is just technical documentation on how to solve a certain problem written for other people to read and use to solve that problem. The act of programming is the act of exploring a problem space. If you have written a program to solve a problem, you have learned the steps needed to solve the problem and can/have solved it if you can prove that it functions correctly.

Because it's not mine and stealing is wrong.

ITT: I never passes Elementary Statistics

>this goddamn reductionism
Why are people so stupid these days?

You can't just reduce to two boxes, you must apply the problem as stated.

fucking lolbertarians

Yes.

Also, 2/3rds.

...

I'll break it down for you guys. Look at the picture:

1. If you have a golden ball from the left box, the next one will definitely be golden.
2. If you have the single golden ball from the middle box, the next one will definitely be silver.

So the naive approach would be: "hey, I already picked a golden ball, so it's 50/50".

The problem is that you don't know WHICH golden ball you have. The chance that you picked one of left box is 10/30 = 1/3. (That's what we expect: "the chance to get one ball from the left box is 1/3").

But the chance that you have a golden ball and grabbed the single golden ball from the middle is only 1/30. If we let 10 million people grab a ball from the a random box and rule out every one that grabbed a silver ball, much more people will have grabbed a ball from the left box.

And how much exactly?
Out of 11 golden balls only 1 is from the box in the middle. The situation to have just grabbed this ball is much more unlikely.

So the answer for the question on my picture would be "10/11 chance that the next ball is golden."

Or for the OP:
"2/3 chance that the next ball wuill also be golden".

Going to have to explain it to you IQ89 retard brainlets.

t. IQ140

Did you drop out of middle school?

This looks like the Bertrand's box paradox, but there is an additional trap.
>next ball you rake from THE SAME BOX will lso be gold?
50% in this case
If you took the one from GG, then you have 100% to take another gold ball
If you took the one from GS, then you have 0% to take another gold ball again
You completely overlook the SS one since it's not possible you are taking another ball from that box.

It would be 2/3 if you weren't forced to pick from the same box

correct

this isn't the same as monty hall at all and the odds are 50%

in monty hall your initial choice is random and then the host's choice cannot be random because he won't ever reveal the goat

in this problem your initial choice is not random across all 3 choices, you are required to pick a box with a golden ball first and the only question is which box you selected from the 2 with golden balls

if you had an actual chance to select the all silver box the odds would be 2/3 but the problem precludes that

Computers have found prime numbers that a programmer wouldn't live long enough to write out.

this right here. your first golden ball is more likely to come from the GG box so the chance is higher than 50%.

...

What a mega fucking troll

No, the first ball being gold was a given, not a factor

I honestly don't know why people are arguing against this. Whoever created this 'puzzle' was a very clever troll. It's a 1-in-2 choice that's been ever so slightly dressed up as a 1-in-3 choice.

>The same box
faggot

FTFY

...

5/6

This is basically the second part of the Monty Hall problem.

The whole point of the Monty Hall problem is that if you have a 1-in-3 chance of picking correctly, then throw out one of those options, you now have a 1-in-2 chance. 50% is a better chance than 33%, thus if you survive the first selection round, you should switch your choice, since the odds become 50%.

This problem is quite literally the second part of that. 50%.

No you you wrong.

The trap is not that we are forced to grab from the same box. The trap is hidden in the sentence "you just grabbed a golden ball".

This does NOT mean: "Take one golden ball from a box of your choice."

But it means: "grab a (silver or golden) ball until it is golden" (of course you mix everything after one attempt, so it' always a start without any further knowledge). We must pay attention on the odds that we picked the one golden ball from the middle.

> the first ball being gold was a given, not a factor

The first ball was give, but WHICH ball?
There are three possible golden balls.

here
Had time to think about it and read some replies here. I considered that the question is vague also.

With replacement: if you take one from the box with two golds, there's a 100% chance of choosing a gold on the second pick. Two times, one for each ball. If you choose the other it's 50% obviously. So (100+100+50)/300 = 5/6.

Without replacement: the two gold box is effectively the same as before, the one gold one silver box is now 0%. So (100+100+0)/300 = 2/3.

I studied maths at uni, I did units on probability theory, and now I'm a maths teacher, I teach this shit on a daily basis.

spread across 2 boxes
once "gold was selected first" became a condition the box with 2 silver balls is now irrelevant

this is nothing like monty hall because in monty hall your initial choice has a chance of being wrong, in this scenario you are required to pick between 2 gold choices at random

But when you think about it, a programmer COULD probably solve even the most difficult yet answerable questions there are given enough time to do so.
Basically the only way for a program to solve something a programmer absolutely is unable to solve, it would have to solve something... I don't even know what.
Even if it solved something we thought was utterly impossible to solve, like finding out the last number of pi, it would probably be possible for humans as well given enough time.

Thus the question posed in OP pretty much can only be answered in a meaningful way if we factor in the limited amount of time humans have in their hands.

This guy explained the relation to monty hall pretty good (trips don't lie):
You see, Bayes' theorem is a bitch. It look like you start from zero, but you have to consider the likelihood of the start situation.

Example:
"One day of the year it snows, the rest of the year it's sunny. If it snows, there's a 60% probability that you find a penny. If it's sunny, there's a 50% probability that you find a penny."

Now when you find a penny, you might think "hey, it's 60% probability to find a penny when it snows, but only 50% when it's sunny."

But now imagine someone calling you and telling you he just found a penny. The probability of a sunny day is just so much higher, that that the lousy 10% more of a snowy day don't really matter.

If you let a guy walk down the street for some days, it's not very likely that he already had the snowy day, but it's very likely that he already found a penny.

let goldfinder () x =
//printfn "Run: %d" x
let urns = [[ "gold"; "gold" ];[ "gold"; "silver" ];[ "silver"; "silver" ]]
let rnd = System.Random()
let nextUrn = rnd.Next(3)
//printfn "Urn: %d" nextUrn
let urn = urns.[nextUrn]
let nextBall = rnd.Next(2)
let ball = urn.[nextBall]
//printfn "First ball: %s" ball
match ball with
| "silver" -> "All silver"
| _ ->
let lastBall = urn.[1-nextBall]
//printfn "Second ball: %s" lastBall
match lastBall with
| "gold" -> "Gold twice"
| _ -> "Gold once"

let ok =
let runs = seq { 0 .. 99999 }
runs
|> Seq.map (fun x -> goldfinder() x)

let result =
ok
|> Seq.countBy id
|> Seq.toList

printfn "%A" result


Is this how it's supposed to work? F#

I just got back from class were we learned Bayes' rule. This is quite a timely demonstration of it's usefulness.

you don't have to consider the likelihood of the start situation because the question precludes it

in monty hall your initial choice is made at random and has a chance to be wrong

in this problem your choice was not made at random across all 3 boxes because the question told you that you were guaranteed to pull a gold ball

the question doesn't ask the average probability of pulling 2 gold if you ran 100 trials selecting a random box

it says "if you pulled out a gold ball as your first choice what is the chance the other ball will be gold" and you had a 50% chance of being right if you were guaranteed to pick gold

this isn't like monty hall because the choice isn't actually random, the monty hall equivalent would be the host removing a goat door before you even make your choice

So let's use Bayes' theorem:

P(A | B) = P(B | A) * P(A) / P(B)


P("the second ball is golden")
= P("you picked from the left box" | "you picked a golden ball")
= P("you picked a golden ball" | "you picked from the left box") * P("you picked from the left box") / P("you picked a golden ball")


We see:
1. P("you picked a golden ball" | "you picked from the left box") = 1
--> after you picked from the left box, the ball is AWLAYS golden

2. P("you picked from the left box") = 1/3
--> we don't care about ball colors here, only about boxes

3. P("you picked a golden ball") = 1/2
--> There are 3 golden and 3 silver balls in this game


P("the second ball is golden") = P("you just picked a golden ball" | "you picked from the left box")

P("the second ball is golden") = 1 * (1/3) / (1/2) = 2/3

Second last line must be:
>P("the second ball is golden") = P("you picked from the left box" | "you picked a golden ball")


And now, for the lulz, let's rule out the right box (with only silver balls) for one moment. The result stays the same:

P("the second ball is golden")
= P("you picked from the left box" | "you picked a golden ball")
= P("you picked a golden ball" | "you picked from the left box") * P("you picked from the left box") / P("you picked a golden ball")


We see:
1. P("you picked a golden ball" | "you picked from the left box") = 1
--> after you picked from the left box, the ball is AWLAYS golden

2. P("you picked from the left box") = 1/2
--> we have only two boxes now

3. P("you picked a golden ball") = 3/4
--> Since we ignore the right box, there are 3 golden and 1 silver balls in this game


P("the second ball is golden") = 1 * (1/2) / (3/4) = 4 / 2*3 = 4 / 6 = 2 / 3

Probabilities, as we understand them right now, are hard wired into the physical laws themselves

> and you had a 50% chance of being right if you were guaranteed to pick gold

And that's where you are wrong.
The question is not: "ignore the chest to the right, take one golden ball from the left and one golden ball from the middle, what will be the next ball be like?"

You just ignore this sentences:
"You pick a ball at random. It is golden."

There are so many explanations in this thread, just pick one and read it carefully..

The Monty Hall problem is similar but different.
You are more likely to pick a door without a donkey (2/3) and the presenter will always open a door with a donkey, which means that by switching you are more likely to get the car.

In this case it is outright stated that you pull a gold ball on the first draw, which means the double silver box ceases to exist.

The chance of pulling a gold ball on the first draw is far more complex, but the chance of pulling a gold ball on the second draw from the same box is just 50%.

To make this into a Monty Hall problem it would need to be more like this.

You pull a ball at random, it's Golden. The presenter takes away the double silver box and then gives you the choice to pick from the same box or pick from the other box. Which do you pick from?
Then you are statistically more likely to get a second golden ball by picking from the other box (okay maybe they take one of the balls out of it as well so they both only have one ball left too)

If I know the setup is 2xg, 2xs, 1xg+1xs then the chances are one in three

open Num;;

let one_draw total success =
let ball1, ball2 =
match Random.int 3 with
| 0 -> true, true
| 1 -> true, false
| 2 -> false, false
| _ -> assert false in
let drawn, next =
match Random.int 2 with
| 0 -> ball1, ball2
| 1 -> ball2, ball1
| _ -> assert false in
if drawn then
let total = total +/ Int 1 in
let success =
if next then
success +/ Int 1
else
success in
total, success
else
total, success
;;

let rec loop total success =
let total, success = one_draw total success in
if mod_num total (Int 1_000_000) = Int 0 then
begin
Printf.printf
"%.2f%%" (100.0 *. float_of_num success /. float_of_num total);
print_newline ()
end;
loop total success
;;

let () =
Random.self_init ();
loop (Int 0) (Int 0)
;;

It converges toward 2/3.

This.
It's 2/3.

Fuck this thread.

The question says, you pick a box at random. Then you take a ball from it and it is gold, so there's one ball left in there. Either gold or silver.

You pick a box at random, you draw a silver ball, what is the chance both balls in the box are gold?

4/3

The important point is the randomness of the box and the pick of the ball.

If you randomly pick a box at random there's 1/3 chance you pick the left box. Now you still have 1/2 chance for the first golden ball and and 1/2 for the second. Why the fuck would someone think it doesn't matter which golden ball you draw? You can't just ecahnge them and threat two balls as one.


0%
No matter which silver ball I pick, there's no way the next ball in the box can add up to "two golden balls".