Logic - 2020-10-19

« first day (1524 days earlier) ← previous day next day → last day (1298 days later) »

11:13 AM

Q: Can the halting problem be solved probabilistically?

Let $H$ be the halting oracle, meaning that $H$ is a function on pairs of strings such that $H(P,X) = 1$ iff $P$ halts on $X$. A probabilistic program is a program that has (oracle) access to a random source. $ \def\pp{\mathbb{P}} $ Can a probabilistic program solve the halting problem with proba...

@user2103480 ^ Do you have any answer or idea about the above question? =)

user2103480

11:38 AM

I think it's a no

The obvious approach would be some reduction to the TM case

Is there some specification on the probability distribution?

user21820

12:25 PM

@user2103480 No specification.

It's my own question, so I get to make the problem as hard as I can hahaha..

I don't see any easy reduction though...

user2103480

I'll just go with inputs as 0-1 strings and the obvious probability distribution, if necessary

does G have to be right?

I'm not sure whether the problem setup is probabilistically unambiguous

We have a probability distribution on all tuples (P,X) right

And I assume you do not mean that for all P, G(P,X) is right for a sufficient proportion of inputs X

Could it be that the right kind of debugger already reaches the threshold for many distributions? Problem is that I don't have a clue how programs check for exceptions in inputs haha

user21820

1:21 PM

What on earth.. someone downvoted my question. Makes no sense!!

@user2103480 The point is that a probabilistic program has to deterministically decide when to access the random source (to get random bits), and must give the right answer with probability more than 1/2.

One cannot take the average success rate over all inputs. For every input, the program must do better than a blind guess.

user2103480

1:47 PM

@user21820 ok because I thought that you meant the average over all cases

user21820

@user2103480 If we just want to be correct on more than 1/2 of all inputs, say by asymptotic density, then note that certain encodings of programs make most (in terms of density) programs total...

So it is the requirement to be biased towards correct for every input that makes it hard.

But we cannot even manipulate the input program because I did not require the bias to be bounded away from 1/2, so if we change the input program the bias for the modified program may very well be closer to 1/2 than for the original.

However, I still think the answer is "no".

« first day (1524 days earlier) ← previous day next day → last day (1298 days later) »

all rooms