0
$\begingroup$

so I was wondering how to know the sequence a Turing machine T computes?

We are reading The Annotated Turing by Charles Petzold at the moment which includes Turing's original paper "On Computable Numbers, with an Application to the Entscheidungsproblem" and adds explanations.

As far as I understand we are looking at circle-free machines, i.e. they will print down more than a finite numbers of symbols of the first kind (which means 0 and 1s).

So there is no end when we can say: "The sequence that is now on the band is the sequence the Turing machine computes". But when are we taking this "snapshot" then? When do we know e.g. that the first digit is "permanent" and that it is the first digit of the sequence that the machine is computing? Maybe the TM writes a million digits and then changes the first digit.

What is about a Turing machine that forever first prints a 0 and then without moving the head prints a 1 and so on? What sequence does this TM compute?

I am sure this question has already been asked but cannot find it so I would also be very thankful for links.

$\endgroup$

1 Answer 1

0
$\begingroup$

How to know the sequence a Turing machine T computes?

Sometimes it's impossible to directly and instantaneously "know" a number, even if it is computable. To say that a machine T computes a number means that it will keep on writing an increasingly large sequence of its digits, properly, when put to work. For many numbers the ability to produce such a machine (or something comparable) is the best thing we have in terms of "knowing", or representing them. You will see that this puts a limit on what can be done with numbers, operationally.

What is about a Turing machine that forever first prints a 0 and then without moving the head prints a 1 and so on? What sequence does this TM compute?

A Turing machine doesn't have to do anything meaningful. Arguably, most of them don't. In fact, there isn't a way of classifying them, or studying them systematically, that doesn't have significant holes. Any "science of Turing machines" will be incomplete - in a nutshell, this is what the paper contends.

$\endgroup$
1
  • 1
    $\begingroup$ Hi Andre, thanks for your answer. I needed some time to think about it. It was very helpful and I think I understand this better now! $\endgroup$
    – KamalaKhan
    Oct 31, 2021 at 5:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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