0
$\begingroup$

I read that the Babbage machine is Turing complete. Which means that no decision Turing machine will halt on the question "does the Babbage machine computes the logarithms of its input?" (for example).

The way I imagine that is there is no finite method (i.e. algorithm) which would examine the Babbage machine, possibly by testing it, but most probably by dismantling it like a watch and concludes that it indeed computes logarithms.

Would that be a correct way of thinking the halting problem on the Babbage machine?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

No. The undecidability of the halting problem for a particular model of computation means that there's no algorithm that takes as input a description of an arbitrary machine $M$ in that model and an input $x$ and determines whether $M$ halts when run with input $x$.

As a consequence, there's no algorithm that takes as input a description of a machine and determines whether that machine computes logarithms. However, that doesn't mean that you can't prove that a specific machine computes logarithms. Indeed, people do this all the time, as exemplified by Knuth's famous quote, “Beware of bugs in the above code; I have only proved it correct, not tried it” (emphasis mine). Proving the code correct requires proving that it terminates and computes the thing it's supposed to compute.

Improve this answer
$\endgroup$
3
  • $\begingroup$ @D.W. ok so I guess the important part here is in that model. I.e. if I were to disprove Rice theorem for that specific Turing machine, I would have to do it using the the same mechanisms and wheels and whatnot which were used to build Babbage machine. Do I interpret your answer correctly? $\endgroup$
    – Jerome
    Apr 11, 2018 at 13:57
  • $\begingroup$ There's no such thing as "Rice's theorem for that specific Turing machine." The whole point of my answer is that you can come up with ad-hoc proofs that some particular machine has some particular property; the difficulty of the halting problem is that it requires a technique to analyze arbitrary machines, rather than just one specific one. $\endgroup$
    – David Richerby
    Apr 11, 2018 at 14:33
  • $\begingroup$ Ah ok Babbage machine is a model of some finite axiomatic theory. As that theory is incomplete (by Gödel), it might be true in some models and false in some other models. Hence Rice just says that it's not possible to find a general way to decide any theorem in that theory (language) otherwise that would contradict the incompleteness. Correct? $\endgroup$
    – Jerome
    Apr 11, 2018 at 15:42
-1
$\begingroup$

I read that the Java programming language is Turing complete.

That means, I can write a Java program such that your Turing machine would not always be able to decide, in a finite number of steps, whether my Java program would terminate after reading some arbitrary input.

It does not mean that every Java program has that property. I can trivially write a Java program that always terminates, and if I do that, then you can construct a Turing machine that always says, "yes, it halts." Or, I can write a Java program that never terminates, and you can construct a Turning machine that always says "no, it doesn't halt."

I don't know the design of Babbage's Analytic Engine, but if it is Turing complete, then that means there is at least one configuration of the engine for which you can not solve the halting problem; but it does not mean that every configuration of the engine has that property.

I don't know what you mean exactly by "computes the logarithm of its input." Babbage's engine was a digital machine, and logarithm is a transcendental function. No digital algorithm to compute the true logarithm of a given number could ever terminate. In a practical configuration of the engine, it would do what my computer's floating-point hardware does: That is, it would compute only the first n digits of the logarithm (for some small n).

I haven't tried asking my computer for the logarithms of every possible double value, but so far, it always has delivered a result in finite time for each of the countless millions of double values that I have tried.

Improve this answer
$\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.