Turing-Recognizable vs. accepted vs. decidable
Mike N. Christoff
"Every decidable language is Turing-recognizable but certain
Turing-recognizable languages are not decidable".
> I think I have these terms distinguished:
>
> L(M) is
> acceptable: if M halts in an accept state
> decidable: if M halts in an accept or reject state
> recognizable: if M halts in an accept/reject state OR loops
>
> My text also says
> Turing recognizable == Recursively Enumerable
> defn:
> Call a language Turing-recognizable (recursively enumerable) if some
Turing
> machine recognizes it.
>
> It also says that 'decidable' == 'recursive'.
> defn:
> Call a language decidable (recursive) if some Turing machine decides it.
>
>
> does this look right?
>
> Thanks, mike
>
> Mike N. Christoff <killallspamme...@sympatico.ca> wrote in
message
> news:t1Id5.217$1h3....@news20.bellglobal.com...
> > Turing-Recognizable vs. accepted vs. decidable
> >
> > What is the difference between a language that is recognizable by a
> Truring
> > machine vs. one that is decidable by a Turing machine?
> >
> >
> > thanks, mike
> >
> >
>
>
>
>
Remi VANICAT
> > I don't know what Turing-recognizable is supposed to mean, either
>
> in the text, they say that "turing-recognizable" and "recursively
> enumerable" are the same thing.
>
So it is exactly what Daniel A. Jimenez have said : a recursively
enumerable language is a language for which there exist a turing
machin that will halt on all string of the language, and no other
string.
My suposition was based on the french version, but it seem there is
some difference.
--
Rémi Vanicat
van...@labri.u-bordeaux.fr
http://dept-info.labri.u-bordeaux.fr/~vanicat
Remi VANICAT
> Turing-Recognizable vs. accepted vs. decidable
>
> What is the difference between a language that is recognizable by a Truring
> machine vs. one that is decidable by a Turing machine?
>
i believed that a language that is recognizable by a Turing machine is
a decidable language.
Mike N. Christoff
L(M) is
acceptable: if M halts in an accept state
decidable: if M halts in an accept or reject state
recognizable: if M halts in an accept/reject state OR loops
My text also says
Turing recognizable == Recursively Enumerable
defn:
Call a language Turing-recognizable (recursively enumerable) if some Turing
machine recognizes it.
It also says that 'decidable' == 'recursive'.
defn:
Call a language decidable (recursive) if some Turing machine decides it.
does this look right?
Thanks, mike
Mike N. Christoff <killallspamme...@sympatico.ca> wrote in message
news:t1Id5.217$1h3....@news20.bellglobal.com...
> Turing-Recognizable vs. accepted vs. decidable
>
> What is the difference between a language that is recognizable by a
Truring
> machine vs. one that is decidable by a Turing machine?
>
>
> thanks, mike
>
>
Mike N. Christoff
Mike N. Christoff
I invite you to continue this discussion in sci.math. :) Much more has
been written.
thanks, mike
Daniel A. Jimenez <djim...@cs.utexas.edu> wrote in message
news:8l7q1l$njq$1...@mamba.cs.utexas.edu...
> In article <cUId5.309$1h3....@news20.bellglobal.com>,
> Mike N. Christoff <killallspamme...@sympatico.ca> wrote:
> >> I don't know what Turing-recognizable is supposed to mean, either
> >
> >in the text, they say that "turing-recognizable" and "recursively
> >enumerable" are the same thing.
>
> "Recursively enumerable" means "Turing-acceptable" in the terminology
> with which I'm familiar. By itself, "recursive" in this context means
> "Turing-decidable," a stronger property. I never liked the subtle lexical
> difference between the terms "recursive" and "recursively enumerable."
> I'd like to be able to abbreviate the latter with the former, but there
> is a big difference between the two.
> --
> Daniel Jimenez djim...@cs.utexas.edu
> "I've so much music in my head" -- Maurice Ravel, shortly before his
death.
> " " -- John Cage
Daniel A. Jimenez
Mike N. Christoff
Mike N. Christoff
> a decidable language.
my text never explains what 'recognizable' means, then it says the
following:
"Every decidable language is Turing-recognizable but certain
Turing-recognizable languages are not decidable".
l8r, mike
Daniel A. Jimenez
I don't know what Turing-recognizable is supposed to mean, either, but
maybe your book means Turing-acceptable. For instance, language of
all (encodings of) halting Turing machines is Turing-acceptable, but
not Turing-decidable. Turing-acceptable means that there exists some
Turing machine that will halt on all strings of the language, and no
other strings. Turing-decidable means that there exists a Turing machine
that will do one thing (e.g. write #Y# on the tape) if a string is in the
language, or another (e.g. write #N# on the tape) if a string isn't in the
language, but the machine will always halt regardless of the string.
Kenneth G. Salter
Mike N. Christoff <killallspamme...@sympatico.ca> wrote in message
news:t1Id5.217$1h3....@news20.bellglobal.com...
> Turing-Recognizable vs. accepted vs. decidable
>
Truring
> machine vs. one that is decidable by a Turing machine?
Accept: Given a string in the language, the Turing machine will halt.
Given a string not in the language, the Turing machine behavior is
unpredictable.
Decide: Given any string, the Turing machine will halt; its output will
tell whether the string belongs to the language.
--
Ken
-------------
Ken Salter mailto:Kenneth...@unisys.com
Unisys Corporation
2476 Swedesford Road voice: 610-648-4455
Malvern, PA 19355 fax: 610-695-5509
Christian Stapfer
>
> Mike N. Christoff wrote in message
> > Turing-Recognizable vs. accepted vs. decidable
> >
> > What is the difference between a language that is recognizable by a
>
> Accept: Given a string in the language, the Turing machine will halt.
> Given a string not in the language, the Turing machine behavior is
> unpredictable.
If only you had been a bit more explicit in what you
mean by the machine's behavior being 'unpredictable'!
If you define the Turing machine's accepting a string
from the language as 'will halt', you *must* define
its rejecting a string that is not in the language as
'will loop'. You *cannot* just write that it will behave
'unpredictably', since halting is also an 'unpredictable'
possibility of behavior but that would be unacceptable
behavior for an acceptor - pun intended.
Christian
J. Antonio Ramirez R.
> [...]
> You *cannot* just write that it will behave
> 'unpredictably', since halting is also an 'unpredictable'
> possibility of behavior but that would be unacceptable
> behavior for an acceptor - pun intended.
That's not true. If M decides a language A, then M also accepts A.
> Christian
--
Antonio
J. Antonio Ramirez R.
> J. Antonio Ramirez R. wrote:
> > Christian Stapfer writes:
> > [...]
> > > You *cannot* just write that it will behave
> > > 'unpredictably', since halting is also an 'unpredictable'
> > > possibility of behavior but that would be unacceptable
> > > behavior for an acceptor - pun intended.
> >
> > That's not true.
>
> You did not consider the *context* in which I wrote the
> above, namely that Kenneth G. Salter wrote:
You are right, I overlooked that what you wrote came after
a hypothetical. My apologies.
> [...much snipped...]
Yes yes yes. I'm wrong. It was a kneejerk reaction. Sorry sorry.
--
Antonio
Christian Stapfer
> Christian Stapfer writes:
> [...]
> > You *cannot* just write that it will behave
> > 'unpredictably', since halting is also an 'unpredictable'
> > possibility of behavior but that would be unacceptable
> > behavior for an acceptor - pun intended.
>
> That's not true.
You did not consider the *context* in which I wrote the
above, namely that Kenneth G. Salter wrote:
> > > Accept: Given a string in the language, the Turing
> > > machine will halt. Given a string not in the language,
> > > the Turing machine behavior is unpredictable.
*If* one want's to define 'accepting a string of the
language' as 'will halt' in this way, without any further
qualification, then, if the machine halts, this means by
definition that the string is *in* the language it accepts.
Thus, a machine that happens to *halt* on a string
*not* in the language *cannot* (according to the first
part of his definition 'halts' := 'accepts') be an *acceptor*
of that language: thus his mistake -- hence my claim.
My point was that *if* one accepts the first part
of his definition ('halts' := 'accepts'), as one might,
the second part of his definition (else 'unpredictable'),
is wrong, if 'unpredictable' is taken to include the
possibility of the machine halting.
> If M decides a language A, then M also accepts A.
That depends on how you define the *details* of 'M accepts A'.
It is certainly true that if a language A is *decidable*,
by M, say, then there exists a machine M' that *accepts*
it: a Turing-decidable *language* is also Turing-acceptable,
but that need *not* imply that the definitions of decidable
and acceptable *must* be arranged in such a way that the
machines, M and M', can be taken to be identical: M = M'.
It *is* possible to define 'accepts' as 'will halt' tout
court, as Kenneth G. Salter suggested, but *if* one does
this, one *must* require the machine to *always* loop if
the input string is not in the language it accepts. Otherwise
his definition becomes vacuous: either the machine halts
or it does not halt, no matter what input string it is
fed - that much is true of all machines.
Since in the case of recursively enumerable but
undecidable languages it is *not* possible to make the
machine *always* halt in a suitable 'reject' state if
the input string is not in the language, one simply
*has* to define the alternative to 'accepts' as 'will
loop' (not, as Kenneth G. Salter suggested: 'behaves
unpredictably'). To introduce, in addition to
'halts' := 'accepts' else loops, a distinction of halt
states (accept and reject halt state) does *not* help
very much but mainly clutters the definition of 'acceptor'.
It would, however, make the claim M = M' valid.
Though such a definitional move does not in any way
refute my criticism of the definition of 'acceptor'
put forth by Kenneth G. Salter. He should have written
that if the input string is in the language the machine
halts in the accept state, and if it is not in the
language it either halts in the reject state *or* loops.
That way to define an acceptor would have been ok,
but that's definitely *not* what Kenneth G. Salter
wrote.
Christian