Estimating run time in the absence of knowledge
No, you can't make any well-justified estimate, if you truly have no knowledge.

In practice, it's rarely that case that we have zero knowledge.  Instead, we might have some idea what the distribution of total computation time will look like.  That gives you a prior.  In other words, before you start the computation, suppose I asked you for your guess at the probability distribution of what the total computation time will be.  What probability distribution would you choose?  The result is a prior.

If you have a prior, then you can compute an estimate for the remaining run time and quantify the uncertainty, using Bayesian analysis.  Let $p(x)$ denote the prior probability that the total computation time is $x$; in other words, before you start running it and before you make any observation, $p(x)$ is your estimate of the probability that it will take $x$ seconds to terminate.

Now we make an observation, and we want to update our estimate of the probability.  We observe that the computation has run for $y$ seconds without terminating yet.  This implies that, whatever the true value of $x$ will turn out to be, it will be at least $y$.  Using Bayes' theorem we obtain

$$\begin{align*}
p(x|y) &amp;= {p(y|x) p(x) \over p(y)}\\
 &amp;= {p(y|x) p(x) \over \int_0^\infty p(y|x) p(x) \; dx}
\end{align*}$$

We notice that we're going to need to know the distribution $p(y|x)$.  This helps us realize that the problem isn't well-stated yet: you haven't told us how you would decide when to make the observation.

Suppose that we decide in advance, before starting the computation, that we're going to wait $y_0$ seconds and then check whether it has halted or not.  Thus there are two possible outcomes of the observation: "already halted" (finished in $\le y_0$ seconds) or "hasn't halted yet" (will take a total of $&gt;y_0$ seconds to finish).  Let's denote those by the outcomes "A" vs "H", so we'll say $y=A$ in the former and $y=H$ in the latter.  Then we find that $p(y|x)$ has the following form: $p(A|x) = 1$ if $x \le y_0$, else $p(A|x)=0$; and the reverse for $p(H|x)$.  Plugging into the formulas above, we obtain

$$\begin{align*}
p(x|A) &amp;= {p(A|x) p(x) \over \int_0^{y_0} p(x) \; dx}\\
p(x|H) &amp;= {p(H|x) p(x) \over \int_{y_0}^\infty p(x) \; dx}
\end{align*}$$

When $x \le y_0$, we have $p(x|H)=0$ (naturally).  When $y_0 &lt; x &lt; \infty$, we see that $p(x|H) = p(x)/q$, where $q = \int_{y_0}^\infty p(x) \; dx$ is the prior probability that $x$ falls in the range $y_0 &lt; x &lt; \infty$.  Here $q$ is a constant that depends on the prior probability; you can think of it as a normalization constant to ensure that $p(x|H)$ is a probability distribution (it integrates to one).

This gives you the posterior distribution for $x$, after running the experiment (starting up the computation and after $y_0$ seconds checking to see whether it has finished yet) and making the observation (that it hasn't finished yet).  From the posterior distribution, you can make estimates for the total running time.  For instance, one reasonable way to make an estimate is to compute the expected value of this posterior distribution.  In this way we obtain

$$\mathbb{E}(x|H) = \int_0^\infty x p(x|H) \; dx = {\int_{y_0}^\infty x p(x) \; dx \over \int_{y_0}^\infty p(x) \; dx}.$$

You can also summarize the uncertainty in  your estimate using a 95% credible interval.

As you can see, all of this machinery requires that we have a prior for the total running time.  Selection of the prior isn't something math can give you; instead, it needs to reflect your domain knowledge and expectations.  Probably you have some ideas for how likely it is that the computation will take a certain amount of time.  For instance, maybe it's common for computations to take anywhere from 1ms to 1 day, but it's rare to run across computations that take (say) 10000 hours -- usually they'll either complete much earlier, or (occasionally) they'll take much longer, but 10000 hours is a lot less likely outcome than 1 hour.   So, constructing a prior is the (subjective) process of quantifying that knowledge you already have.  Alternatively, the choice of prior might be informed by data, if you collect a data set of how long other computations have taken to complete and use that to fit some kind of distribution to them.

Once you've chosen a prior, then you can use the mathematics shown above to estimate how long the running time will turn out to be, in a methodologically sound way.