문제

Can a probabilistic Turing Machine compute an uncomputable number?

My question probably does not make sense, but, that being the case, is there a reasonably simple formal explanation for it. I should add that I am pretty much ignorant of probabilistic TM and randomized algorithms. I looked at wikipedia, but may even have misunderstood what I read.

The reason I am asking that is that only the computable numbers can have their digits enumerated by a Turing Machine.

But with a probabilistic Turing Machine, I can enumerate any infinite sequence of digits, hence also sequences corresponding to non computable numbers.

Actually, since there are only countably many computable numbers, while there are uncountably many reals that can have their digit enumerated, I could say that my probabilistic Turing Machine can be made to enumerate the digits of a non computable number with probability 1.

I believe this can only be fallacious, but why? Is there a specific provision in the definition of probabilistic TM that prevents that?

Actually, I run into this by thinking whether various computation models can be simulated by a deterministic TM, in question "Are nondeterministic algorithm and randomized algorithms algorithms on a deterministic Turing machine?". Another p[ossibly related question is "Are there any practical differences between a Turing machine with a PRNG and a probabilistic Turing machine?".

올바른 솔루션이 없습니다

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 cs.stackexchange
scroll top