Find a new automata ,it's language is only Recursive Lanauge. - Theory

Dnia 27-10-2008 o 05:33:21 manonhill <manonhill@yeah.net> napisa³(a):

> I would like to know what do you think of this idea. I know this
> is a crazy idea, but this idea may be right.

It can't be right - there's no effective description for the set of all
recursive languages.


--
Micha³ Przyby³ek

What you want to do is quite difficult.

The problem is to take an automata that cannot handle recursive
languages and add some mechanism that allows it to handle recursive
languages without also allowing it to handle recursively enumerable
languages. Typically, the mechanism that is added is a way to store
the current state of the machine on a tape so the machine can "wind"
and "unwind" itself through the recursive structure. Unfortunately,
this kind of mechanism is exactly what is needed to support the
recursively enumerable languages.

The PDA's and LBA's do something similar to what you want by limiting
what can be put on the tape and when. However, neither type of these
machine supports the full set of recursive languages. So, the closest
we normally get are the CSL's by selecting a language specification
that places a linear bounds on the size of the tape. The CFL's and
CSL's carefully restrict the languages they match to situations where
you always know that you are progressing toward a positive or negative
result.

With the full recursive languages you can find cases where even though
the language is only recursive, you cannot prove from the language's
grammer that you are alway progressing toward an answer. These are
cases where the language needs to be defined with an unrestricted
grammer, but is still recursive. However this puts us back in the
same position again. We cannot tell (from the grammer) what is
recursive and what is recursively enumerable.

On a positive note, if you could build an automata like the one you
want, it would not suffer from the halting problem. Membership in a
recursive language is a decidable problem so the automata would always
halt.

Dnia 28-10-2008 o 09:13:20 Joe Schafer <joe@joeschafer.com> napisa³(a):

> On a positive note, if you could build an automata like the one you
> want, it would not suffer from the halting problem. Membership in a
> recursive language is a decidable problem so the automata would always
> halt.

What?...

Damn. The whole thing about automata/grammars is that _simple_ syntactic
rules give powerfull constraints on the set of definable languages. The
property of being a recursive language is _undecidable_, so the only way
to define automata that accept recursive languages is to put _undecidable_
constraints on syntax.

For example, you may define these automata as follows: ,,A Turing machine
that accepts a recursive language''. Are you delighted with this
definition?


--
Micha³ Przyby³ek

> Damn. The whole thing about automata/grammars is that _simple_ syntactic
> rules give powerfull constraints on the set of definable languages. The
> property of being a recursive language is _undecidable_, so the only way
> to define automata that accept recursive languages is to put _undecidable_
> constraints on syntax.

Yes exactly, If you COULD build an automata that ONLY matched
recursive languages, this would imply you have a solution to the
halting problem.
Any full TM will halt and match recursively enumerable languages as
long as the input is actually a member of the language.
But how would you exclude those languages? This IS the crux of the
halting problem.

> For example, you may define these automata as follows: ,,A Turing machine
> that accepts a recursive language''. Are you delighted with this
> definition?

But a TM that ALWAYS halts on a given language is the definition of a
recursive language.
So how is that any different from a normal full Turing machine with
its normal halting problem???

Dnia 28-10-2008 o 22:41:55 Joe Schafer <joe@joeschafer.com> napisa³(a):

>> Damn. The whole thing about automata/grammars is that _simple_ syntactic
>> rules give powerfull constraints on the set of definable languages. The
>> property of being a recursive language is _undecidable_, so the only way
>> to define automata that accept recursive languages is to put
>> _undecidable_
>> constraints on syntax.
>
> Yes exactly, If you COULD build an automata that ONLY matched
> recursive languages, this would imply you have a solution to the
> halting problem.

No, unless the construction is effective.

>> For example, you may define these automata as follows: ,,A Turing
>> machine
>> that accepts a recursive language''. Are you delighted with this
>> definition?
>
> But a TM that ALWAYS halts on a given language is the definition of a
> recursive language.
> So how is that any different from a normal full Turing machine with
> its normal halting problem???

Let's take the concept of pushdown automata. We may think of pushdown
automata as of turing machines with the restriction: ,,all operations can
be preformed only at the end of the tape''. Similarly, we may think of our
automata as of turing machines with the restriction: ,,the language have
to be recursive''.

The difference between these two definitions is that in the first case the
restriction is ,,computationally effective'', wheares in the other case it
is highly nontrivial.



--
Micha³ Przyby³ek

So do you know of an effective test for recursiveness???? One that
always halts!!!

I would sure be interested in how you intend to guarantee that
mutually recursive constructs in the grammer don't create infinite
loops. They appear to me to be just the same as the mutually
recursive constructs in a recursively enumerable language that create
the halting problem.

In any case, if you saying that we define an "only recursive
automata" by simply taking a TM and only loading it with known
recursive languages, what's the point??? We know those calculations
are always total and it doesn't add anything to what we already know
about TM's. I can load a regular language into a PDA and it works
just fine. But that doesn't tell me anything new about regular
languages or PDA's.

Dnia 30-10-2008 o 23:18:06 Joe Schafer <joe@joeschafer.com> napisa³(a):

> So do you know of an effective test for recursiveness???? One that
> always halts!!!

What?...

> I would sure be interested in how you intend to guarantee that
> mutually recursive constructs in the grammer don't create infinite
> loops. They appear to me to be just the same as the mutually
> recursive constructs in a recursively enumerable language that create
> the halting problem.

What?... I'm not kidding. I don't follow your logic. I said that your
sentence:

,,If you COULD build an automata that ONLY matched recursive languages,
this would imply you have a solution to the halting problem.''

is wrong, and explained why it is wrong. Your imagination is really
impressive.

> In any case, if you saying that we define an "only recursive
> automata" by simply taking a TM and only loading it with known
> recursive languages, what's the point???

What? Do you know the definition of a Turing machine?

> We know those calculations
> are always total and it doesn't add anything to what we already know
> about TM's. I can load a regular language into a PDA and it works
> just fine. But that doesn't tell me anything new about regular
> languages or PDA's.

Modulo the strange term ,,load'' - sure, that's what I tried to say.


--
Micha³ Przyby³ek