Re: Yet another contribution to the P-NP question

So, it goes without saying, I would not have wanted you to reply to this
draft. I was typing out my reply, then I realized that I hadn't
completely thought out the decider of L_P.
It seems that what made the assertion so self-evident was that I was
assuming the role of a decider and it was obvious to me that I just had
to look at all the cases.
But if I dissociate myself from the decider, I could now ask, 'why does
the decider have to look at everything?' (And my answer is because all
possible outcomes are consistent with everything the decider has been
given a priori).
I realized I couldn't think through this that night, so tried to save my
draft and reply when I had it all, but I somehow sent it anyway.

Not really.  The term tuple has been accepted as the way to talk about
finite ordered lists (pairs, triples, etc.).  The term sequence has
always been used for infinite indexed... well... sequences.
>

Okay.

OK.  So "over" is hiding something.  M is not a map from U_M* to U_M*.
That's messy and seems to be unnecessary.  What is the problem in saying
that strings M maps?  Why not simply allow M's domain to contain all the
string that it might "operate on"?
>

My reply for this is that I started thinking of M as a skin (or a mask?)
over a Turing machine, so my initial definition of M involves iterating
over sections of the input string and not the strings themselves (same
difference, I suppose).
But another reply is that I actually wanted to provide simpler
definitions. The only feature I really need to preserve is that parts of
strings can be changed to other strings; everything else is degenerate.
But I suspect the reason is that there is no good reason why :) I just
wrote it that way and haven't shown anyone, so no one has said,
"Nnymous, that is a strange way to do things..."
Of course, I'm always open to making things cleaner if they facilitate
communication.

>
I was talking about the details.  They look clumsy to me.  What you say
below is straightforward and obvious.
>

Could you explain what you mean by clumsy? To be fair, I'd probably also
need to understand what you meant by 'weak' first.

That's fine and not all surprising.  This does not require the odd
detail that M's domain does include all the string it might be applied
to!
>

I could always rework this down the line.

Then we can say that S.(M(x)) satisfies the property {q_accept} and
becomes stationary at iteration i to capture the same halting idea.

>
Yes, I can see you might want to do that.  I suspect there will be a
simpler way to describe the properties you are interested in, but that's
not important right now.
>

Again, I rewrote this as I would not have liked to reply this way, but I
shall reply to your replies anyhow

Fine.  By the way, you don't need to name everything:
>
   s in S iff S.(R(s)) satisfies {q_accept}
   s not in S iff S.(R(s)) satisfies {q_reject}
>
though you really should make it clear that {q_accept} is not what it
appears -- a set containing a state -- it's a set containing a string of
length one.

>

Okay, noted.

>
1) We need to specify that the property satisfaction takes place after
the computation has become stationary.

>
That is not part of your definition of "satisfies" but it will, of
course, follow from the fact that the result of your iterations are TM
configurations and they always become constant when that state is either
q_accept or q_reject.
>
If did not go off into your own notation, there would be no need to
worry about this being obvious.
>

I really would have liked to leave this point out at this stage. This is
a technicality stemming from my degenerate definitions. In general, a
recursion need not be built from a TM and need not contain q_accept and
q_reject as symbols.

2) Also, R need not be constructed from a TM or have q_accept or
q_reject in U_R (i.e., in the set it "recurses" over), so P1 and P2 need
only be two properties that a computation cannot both satisfy at the
same time when it is stationary*.

>
OK.  You've lost me.  I thought R (and iteration) was always a TM
configuration transition function.
>
This must be cleared up, because non-computable maps are going to take
you into all kinds of murky waters.

Yup, I should have left this out until we started talking specifics, but
in general R need not be a TM configuration transition function. It's
just a bunch of tuples that have some structure and R(s) is some result
you get if you apply the rules prescribed by R.
Now, we can construct a bunch of these from TMs, so that they have
special properties like whenever a string appears with q_accept, the
outputs of R becomes stationary.
Of course if this recursion was being performed by a TM[*], such a TM
may accept or reject as is necessary, but from the point of view of the
recursion, there is no q_accept or q_reject in the set it recurses over.

>

3) And R need not act on S directly, we only need a surjective function,
f, to map strings that R can "recurse" over, that is from (U_R)* to some
superset of S [*]

>
Again you've lost me.  I no longer know what it means for an iteration
(what was a recursion) to decided something.
>

So, to decide L_P,

>
Ah, this sudden stop made me go look to see of there was another post.
And there is, and it suggests you plan to offer a different argument.  I
hope I have not wasted my time here.

I mean, I certainly hope not. At the very least, you would have educated
a stranger over the internet on the rudiments of computing theory :)
Also, it's not a different argument. It's more of a change in
perspective.
I had to write one more paragraph (and I suppose we could even subsume
its key ideas into another section) to clarify what deciding a language
would mean in this context, and I had to rewrite another section.
The words are different, but the thinking is the same (when we get to
discussing the text, I would be happy to highlight changes between both
versions).
[*] - Now there's been a subtle (?) shift here which may need me to
re-explain certain things.
Previously, I have been talking about these recursions as another system
of computation assuming that you could use them in place of a TM or
something similar.
But this isn't quite accurate. They actually can't decide things, for
example, so you'd still need something to do the deciding. But I think
the way they have been set up allow them to be useful for other things.