Probabilistic methods for undecidable problem

An undecidable problem is a decision problem proven to be impossible to construct an algorithm that always leads to a correct yes-or-no answer. I wonder if there are examples of probabilistic approaches (in the following sense below) that solve such problems.

By a probabilistic approach, I mean a nondetermistic algorithm such that for each input it outputs in finite time and the answer is correct with probability strictly larger than $50\%$. In other words, it is similar to PP but I do not require polynomial time (shall I call it "FiniteP", or it has a name already in complexity theory?). Please do not confuse this with a nondetermistic algorithm that performs probabilistically, but still tries to find a definite answer before halting.

So, we have a TM $M$ that can in addition flip a fair coin. We have the promise that for every input $M$ will eventually halt and give an answer, no matter what the coin results are. Moreover, we demand that the probability of getting the correct answer is greater than 0.5.

First let us observe that because $2^\omega$ is compact, we can move from "For every sequence of coin tosses there is a finite time $t$ where $M$ halts" to "There is a finite time $t$ such that $M$ halts by time $t$ regardless of the coin outcome". This in turn means that for each input to $M$, there are only finitely many (no more than $2^t$) many computation pathes that are possible.

A deterministic machine $N$ can simulate what $M$ would do for each of the finitely many coin results. As more than half of these return the correct answer, a simple majority vote suffices for $N$ to figure it out.

So your class FiniteP consists of exactly the decidable problems.

StackExchange Computer Science Q#154615, answer score: 19