0
$\begingroup$

Not sure precisely how to ask this question, but I want to understand if it is meaningful to ask about probabilities when aspects of the definition might be undecidable. My curiosity extends to potential implications for definitions of entropy in physical systems. Let me try to get a little more precise about the question, and maybe someone can point me in the direction of papers or textbooks that address the topic, or has an answer themselves.

For example, imagine I have a dynamical system which can be mapped to a universal Turing machine, so there are some input settings where I can map the outputs to Halting vs not. Now some inputs are chosen at random, and I want to know the probability that the machine halts or not. Does the fact that knowing if the problem halts on the input or not is undecidable imply that the a probability measure is ill-defined in this case? Are there any implications for probability of input or output in such a case?

$\endgroup$
1
$\begingroup$

The space of possible inputs of a Turing machine is countable, so all its subsets are measurable. Same for outputs.

However, it's possible that this probability is not computable. In particular, you may want to look up Chaitin's constant. It isn't exactly what you are talking about, but closely related.

$\endgroup$
1
$\begingroup$

You might never be able to know if a turing machine halts or does not halt for an input. It still either does halt or does not. Thus it depends on other things if the probability that the turing machine halts for a specific distribution of inputs is well defined; not on actually knowing if it halts.

There are no implications for the probability itself, other than that you are unlikely to ever know what the probability is. To put it another way, think about betting on the turing machine halting. If you are able to determine the random input according to the distribution, then there will be a winner. You just do not know who it is and thus are unfortunately not able to settle the bet.

Another analogy is a bet on an event that everyone is unable to observe. It either will have happened or not. There will be a winner. You just do not know who it is...

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.