0
$\begingroup$

I've got a basic doubt for such I'm not getting convicting argument. See,

We say a TM $M$ is Turing recognizer if it accepts a string belonging to the language $L(M)$ & says $yes$ if the string belongs to it. But how it will know when it should stop to arrive at decision? For e.g, suppose there is a string $w$ which belongs to $L$ but it is extremely long so that it will take some 1000 years for TM $M$ to recognize the string. So how TM $M$ will accept the string now & affirm it belongs to the language? If it can't affirm now then why it is even a Turing recognizer.

Improve this question
$\endgroup$
  • 1
    $\begingroup$ Nowhere does the definition say that the recognizer has to work instantly. It can take any finite amount of time to arrive at the decision. $\endgroup$ – Andrej Bauer Jan 28 '18 at 10:19
  • $\begingroup$ @Andrej It's okay. But then how do we know Turing recognizer accepts a particular string? $\endgroup$ – Mr. Sigma. Nov 21 '18 at 2:51
  • $\begingroup$ It is irrelevant what "we know". "We" are not the machine and "we" are not part of mathematics. The definition of recognizer makes sense even if there are no human beings. You should reformluate your question so that you do not metion "we", "humans", or "know". It is also forbidden to say "machine knows" because that does not make any sense. Furthermore, in computability theory there is no notion of time. A machine performs a certain number of steps during computation, but that does not mean that there is time. There is just the number of steps. What is your question? $\endgroup$ – Andrej Bauer Nov 21 '18 at 17:08
5
+50
$\begingroup$

First, Turing machines don't "recognize" strings: they either reject or accept them. "Recognize" is a word we apply to languages, i.e., sets of strings. I think that might be an important point because the way you write suggests that you think that a Turing machine recognizing a string means that it looks at it for a bit and then says, "Oh, yes, I see. That's a string I'll accept if I'm given it as input." That's not what happens at all.

You can think of a Turing machine as a computer program. It's given a string as its input and it starts running. It just follows its instructions and does whatever it's supposed to do. It might eventually stop and accept; it might eventually stop and reject; it might never stop at all. It stops when its programming tells it to stop, just like any other computer program.

A Turing machine recognizes a language $L$ if, for each string $w\in L$, it eventually stops and accepts and, for each string $w\notin L$ it either never stops or it stops and rejects. This isn't any normal English-language use of the word "recognize", which might be what has confused you.

Note that, in general, there's no way to predict whether or not a Turing machine will stop: this is the famous undecidability of the halting problem. So, if you had a real-life physical Turing machine (or any other computer program) and it had been running for an hour and still hasn't finished, there's no general technique that will tell you if it will ever finish. So, if you were using your real-life Turing machine to recognize some language, there would be three possibilities for any input: "The Turing machine ran to completion and said yes", "The Turing machine ran to completion and said no" and "The Turing machine is still running, so I don't know." Mathematically, this isn't a problem – we define the string to be in the language if it would accept if we waited long enough, even though that might not be physically possible.

Improve this answer
$\endgroup$
2
$\begingroup$

There is no restriction on how long a recognizer $M$ takes to accept as long as for any $w \in L(M)$, $M$ eventually accepts in some finite amount of time, even if it's horribly inefficient. That is, there is no notion of "affirm now" because computability theory (recognizability, decidability, etc.) doesn't take into consideration how long computations will take and is just interested in "What problems can we solve/verify at all with computers?"

There's a separate question of "What problems can we solve/verify efficiently?" This is the field of complexity theory, in which computation time is one possible way of measuring efficiency.

Improve this answer
$\endgroup$
  • $\begingroup$ Then how TM will predict in prior that a particular string gonna be accepted after 1000 years? $\endgroup$ – Mr. Sigma. Jan 28 '18 at 5:59
  • 2
    $\begingroup$ @Rajas. It doesn't predict anything. It just gets run on the particular input and if it takes a thousand years to run, that's how long it takes. $\endgroup$ – David Richerby Jan 28 '18 at 11:21
  • 1
    $\begingroup$ @Rohith. We don't whether it will eventually accept, as my answer already explains. $\endgroup$ – David Richerby Nov 21 '18 at 9:30
  • 2
    $\begingroup$ @Rohith. I already explained all of this in my answer. The machine either halts and accepts, halts and rejects or doesn't halt. There is no way to tell except by running the machine. If you run it for a long time and it still hasn't halted, there is no way to tell if it will halt in the future, except by running the machine even longer . $\endgroup$ – David Richerby Nov 21 '18 at 9:50
  • 1
    $\begingroup$ What David says is true, in general, mathematically speaking. Practically speaking, many Turing machines (= computer programs) are tractable enough so that we know that the halt (those are deciders), and even roughly when they will finish (that's what algorithm analysis is about). But the fact remains that no Turing machines (!) can decide for all (!) Turing machines whether or when they halt. $\endgroup$ – Raphael♦ Nov 21 '18 at 11:33

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.