Please forgive me, for I may not be able to review your own proof at the moment. Moreover, the links you provide point to things that seem like software packages. Might you be able to direct me to the PDF (or a
similar sort of file)?
Regarding the DOI I provided, you should be able to use it by inputting
it into this website: https://dx.doi.org/
Also, I did not know this yesterday, but alternatively, you can access
the document directly through the following link: https://figshare.com/articles/preprint/On_Higher_Order_Recursions_25SEP2024/27106759?file=49414237
On 2024-09-26 08:57, nnymous109 wrote:
Please forgive me, for I may not be able to review your own proof at the
moment. Moreover, the links you provide point to things that seem like
software packages. Might you be able to direct me to the PDF (or a
similar sort of file)?
Regarding the DOI I provided, you should be able to use it by inputting
it into this website: https://dx.doi.org/
Also, I did not know this yesterday, but alternatively, you can access
the document directly through the following link:
https://figshare.com/articles/preprint/On_Higher_Order_Recursions_25SEP2024/27106759?file=49414237
Neither of those methods work. I don't think you correctly uploaded the file.
Andr�
On 26/09/2024 18:57, André G. Isaak wrote:
On 2024-09-26 08:57, nnymous109 wrote:
Please forgive me, for I may not be able to review your own proof at the >>> moment. Moreover, the links you provide point to things that seem like
software packages. Might you be able to direct me to the PDF (or a
similar sort of file)?
Regarding the DOI I provided, you should be able to use it by inputting
it into this website: https://dx.doi.org/
Also, I did not know this yesterday, but alternatively, you can access
the document directly through the following link:
https://figshare.com/articles/preprint/On_Higher_Order_Recursions_25SEP2024/27106759?file=49414237
Neither of those methods work. I don't think you correctly uploaded
the file.
André
The following worked for me:
<https://doi.org/10.6084/m9.figshare.27106759>
You can view the doc ("On Higher Order Recursions") in the browser, or
there is a link on the page to download a PDF.
On 27/09/2024 23:42, Ben Bacarisse wrote:
Mike Terry <[email protected]> writes:Not a joke, for sure. Stuff like the integral sign needs explanation. Paragraph [5] looks like a definition? or is it standard in some branch of computation theory? I haven't seen it used like that, but wouldn't really know.
On 27/09/2024 00:34, Ben Bacarisse wrote:Later he/she writes
[email protected] (nnymous109) writes:
Also, I did not know this yesterday, but alternatively, you can access >>>>> the document directly through the following link:I am hoping that this is a joke. If it is a joke, then I say well done >>>> sir (or madam)[*].
https://figshare.com/articles/preprint/On_Higher_Order_Recursions_25SEP2024/27106759?file=49414237
But I fear it is not a joke, in which case I have a problem with the
first line. If you want two of the states to be symbols (and there are >>>> points later on that confirm that this is not a typo) then you need to >>>> explain why early on. You are free to define what you want, but a paper >>>> that starts "let 2 < 1" will have the reader wrong-footed from the
start.
You mean q_accept and q_reject? It looks like they are just to represent >>> the accept and reject states, not tape symbols? Calling them symbols is >>> like calling q_0 a symbol, which seems harmless to me - is it just that you >>> want to call them "labels" or something other than "symbols"?
(Omega U {q_accept, q_reject})*
where * is, presumably, the Kleene closure. Omega is the set of
non-blank tape symbols of the TMs under discussion so these states are
used to make "strings" with other tape symbols.
I agree that what the states actually are is irrelevant, but that two of
them are later used like this is presumably important.
I don't fully get the notation though - e.g. it seems to me that the TMs >>> have tape symbols and states, but I don't see any state transitionRight, but that's line 2 and I was starting at line 1!
table!
I thought it might be joke because of the way the author just piles
definition on definition using bizarre notations like integral symbols
but apparently not.
When someone turns up from outside the established academic establishment with their own proof it can be hard work deciphering what they're really trying to say - so many private notations to clarify and so on. Many
experts reasonably decide they're unable/unwilling to invest enough time on something very likely to turn out a lost cause. Anyhow, I hope this thread gets somewhere as it's likely I'll learn something here!
Of course the paper is very very likely wrong, and likely for a common underlying reason for such proof attempts, but the author says as much and asks for assistance rather than insisting they know better than all the experts - so a million miles from the usual class of usenet cranks we typically see. [PO, WM, AP, Nam/KD, JSH etc... all duffers in the sense of lacking background + ability to express themselves and reason technically, but not recognising this for whatever reasons. Ok, WM might be in his own category as he supposedly has more background than those others.].
It's funny - this group has had years and years of the likes of PO and his nonsense claims. It might seem almost like providence that just a couple
of days after PO moves on (as it appears he has?)
someone should turn up
with a new thread containing (hopefully) actual logical argument rather
than a succession of PO-non-logical claim after claim with no logic!
Almost like this is what a group like this was originally meant for!
:)
Ben Bacarisse <[email protected]> writes:
Mike Terry <[email protected]> writes:[...]
[...]It's funny - this group has had years and years of the likes of PO and his >>> nonsense claims. It might seem almost like providence that just a couple >>> of days after PO moves on (as it appears he has?)
I have been filtering his posts for some time, but now you mention it,
yes he's vanished. I fear he was telling the truth about his health and
he may be very ill now.
His most recent post was from Sep 21, 7 days ago, subject "Enough of
losers stuck in rebuttal mode", no body.
On Fri, 27 Sep 2024 22:42:31 +0000, Ben Bacarisse wrote:
Mike Terry <[email protected]> writes:
On 27/09/2024 00:34, Ben Bacarisse wrote:
[email protected] (nnymous109) writes:
Also, I did not know this yesterday, but alternatively, you can access >>>>> the document directly through the following link:I am hoping that this is a joke. If it is a joke, then I say well done >>>> sir (or madam)[*].
https://figshare.com/articles/preprint/On_Higher_Order_Recursions_25SEP2024/27106759?file=49414237
But I fear it is not a joke, in which case I have a problem with the
first line. If you want two of the states to be symbols (and there are >>>> points later on that confirm that this is not a typo) then you need to >>>> explain why early on. You are free to define what you want, but a paper >>>> that starts "let 2 < 1" will have the reader wrong-footed from the
start.
You mean q_accept and q_reject? It looks like they are just to
represent
the accept and reject states, not tape symbols? Calling them symbols is >>> like calling q_0 a symbol, which seems harmless to me - is it just that
you
want to call them "labels" or something other than "symbols"?
Later he/she writes
(Omega U {q_accept, q_reject})*
where * is, presumably, the Kleene closure. Omega is the set of
non-blank tape symbols of the TMs under discussion so these states are
used to make "strings" with other tape symbols.
I agree that what the states actually are is irrelevant, but that two of
them are later used like this is presumably important.
I don't fully get the notation though - e.g. it seems to me that the TMs >>> have tape symbols and states, but I don't see any state transition
table!
Right, but that's line 2 and I was starting at line 1!
I thought it might be joke because of the way the author just piles
definition on definition using bizarre notations like integral symbols
but apparently not.
Okay, Ben. Please allow me to try again.
I'm not completely sure how to use USENET to reply to portions of
replies, so I will try to answer some of your queries here since the
other reply is much longer.
I don't actually use the Turing machines formalism at all in my
arguments until about point 22, so throughout the document I'm not
thinking about Turing machine states and Turing machine symbols and
Turing machine configurations, at all.
But in trying to discuss with others, I tend to just cast the entire
argument in the language of Turing machines, since I felt that that
would be more familiar. Maybe I shouldn't have done that.
It's probably more accurate to say that I am trying to come up with a
string re-writing model of computation as you pick up on. So everything
is a string, and everything that can be used to form a string is a
symbol, so there's no semantic difference between the following strings:
0 0 1 0 0 0 1
1 1 q_a r_e 0 0 2 3 d
q_accept q_reject q_accept 1 1 q_reject 0 0 0 d f g
Then we have some rules that tell us to replace substrings of any given string with another string. That's the entire recursion idea (and yes,
we could do this with a Turing machine, but I'm asking us to forget
about Turing machines momentarily).
Also, rather than do a wall of text like last time, I think I should
pause and ask for criticisms here, and then answer them/proceed as is necessary.
Mike Terry <[email protected]> writes:
On 27/09/2024 23:42, Ben Bacarisse wrote:
Mike Terry <[email protected]> writes:Not a joke, for sure. Stuff like the integral sign needs explanation.
On 27/09/2024 00:34, Ben Bacarisse wrote:Later he/she writes
[email protected] (nnymous109) writes:
Also, I did not know this yesterday, but alternatively, you can access >>>>>> the document directly through the following link:I am hoping that this is a joke. If it is a joke, then I say well done >>>>> sir (or madam)[*].
https://figshare.com/articles/preprint/On_Higher_Order_Recursions_25SEP2024/27106759?file=49414237
But I fear it is not a joke, in which case I have a problem with the >>>>> first line. If you want two of the states to be symbols (and there are >>>>> points later on that confirm that this is not a typo) then you need to >>>>> explain why early on. You are free to define what you want, but a paper >>>>> that starts "let 2 < 1" will have the reader wrong-footed from the
start.
You mean q_accept and q_reject? It looks like they are just to represent >>>> the accept and reject states, not tape symbols? Calling them symbols is >>>> like calling q_0 a symbol, which seems harmless to me - is it just that you
want to call them "labels" or something other than "symbols"?
(Omega U {q_accept, q_reject})*
where * is, presumably, the Kleene closure. Omega is the set of
non-blank tape symbols of the TMs under discussion so these states are
used to make "strings" with other tape symbols.
I agree that what the states actually are is irrelevant, but that two of >>> them are later used like this is presumably important.
I don't fully get the notation though - e.g. it seems to me that the TMs >>>> have tape symbols and states, but I don't see any state transitionRight, but that's line 2 and I was starting at line 1!
table!
I thought it might be joke because of the way the author just piles
definition on definition using bizarre notations like integral symbols
but apparently not.
Paragraph [5] looks like a definition? or is it standard in some branch of >> computation theory? I haven't seen it used like that, but wouldn't really >> know.
When someone turns up from outside the established academic establishment
with their own proof it can be hard work deciphering what they're really
trying to say - so many private notations to clarify and so on. Many
experts reasonably decide they're unable/unwilling to invest enough time on >> something very likely to turn out a lost cause. Anyhow, I hope this thread >> gets somewhere as it's likely I'll learn something here!
I tried to make one major suggestion to the author: explain (in English)
in what way the core of the argument differs from the usual "it must
examine all the cases" non-proofs that keep cropping up.
Of course the paper is very very likely wrong, and likely for a common
underlying reason for such proof attempts, but the author says as much and >> asks for assistance rather than insisting they know better than all the
experts - so a million miles from the usual class of usenet cranks we
typically see. [PO, WM, AP, Nam/KD, JSH etc... all duffers in the sense of >> lacking background + ability to express themselves and reason technically, >> but not recognising this for whatever reasons. Ok, WM might be in his own >> category as he supposedly has more background than those others.].
But there are some worrying signs. If someone knows little mathematics,
why describe a mapping as a homomorphism when there is no topology in
play? Does he or she just mean a bjection? What has continuity to do
with it? There's a whiff of "that's a nice sounding word, I'll use it"
here.
On 29/09/2024 01:30, Ben Bacarisse wrote:
Mike Terry <[email protected]> writes:
On 27/09/2024 23:42, Ben Bacarisse wrote:I tried to make one major suggestion to the author: explain (in English)
Mike Terry <[email protected]> writes:Not a joke, for sure. Stuff like the integral sign needs explanation.
On 27/09/2024 00:34, Ben Bacarisse wrote:Later he/she writes
[email protected] (nnymous109) writes:
Also, I did not know this yesterday, but alternatively, you can access >>>>>>> the document directly through the following link:I am hoping that this is a joke. If it is a joke, then I say well done >>>>>> sir (or madam)[*].
https://figshare.com/articles/preprint/On_Higher_Order_Recursions_25SEP2024/27106759?file=49414237
But I fear it is not a joke, in which case I have a problem with the >>>>>> first line. If you want two of the states to be symbols (and there are >>>>>> points later on that confirm that this is not a typo) then you need to >>>>>> explain why early on. You are free to define what you want, but a paper >>>>>> that starts "let 2 < 1" will have the reader wrong-footed from the >>>>>> start.
You mean q_accept and q_reject? It looks like they are just to represent >>>>> the accept and reject states, not tape symbols? Calling them symbols is >>>>> like calling q_0 a symbol, which seems harmless to me - is it just that you
want to call them "labels" or something other than "symbols"?
(Omega U {q_accept, q_reject})*
where * is, presumably, the Kleene closure. Omega is the set of
non-blank tape symbols of the TMs under discussion so these states are >>>> used to make "strings" with other tape symbols.
I agree that what the states actually are is irrelevant, but that two of >>>> them are later used like this is presumably important.
I don't fully get the notation though - e.g. it seems to me that the TMs >>>>> have tape symbols and states, but I don't see any state transitionRight, but that's line 2 and I was starting at line 1!
table!
I thought it might be joke because of the way the author just piles
definition on definition using bizarre notations like integral symbols >>>> but apparently not.
Paragraph [5] looks like a definition? or is it standard in some branch of >>> computation theory? I haven't seen it used like that, but wouldn't really >>> know.
When someone turns up from outside the established academic establishment >>> with their own proof it can be hard work deciphering what they're really >>> trying to say - so many private notations to clarify and so on. Many
experts reasonably decide they're unable/unwilling to invest enough time on >>> something very likely to turn out a lost cause. Anyhow, I hope this thread >>> gets somewhere as it's likely I'll learn something here!
in what way the core of the argument differs from the usual "it must
examine all the cases" non-proofs that keep cropping up.
Of course the paper is very very likely wrong, and likely for a commonBut there are some worrying signs. If someone knows little mathematics,
underlying reason for such proof attempts, but the author says as much and >>> asks for assistance rather than insisting they know better than all the
experts - so a million miles from the usual class of usenet cranks we
typically see. [PO, WM, AP, Nam/KD, JSH etc... all duffers in the sense of >>> lacking background + ability to express themselves and reason technically, >>> but not recognising this for whatever reasons. Ok, WM might be in his own >>> category as he supposedly has more background than those others.].
why describe a mapping as a homomorphism when there is no topology in
play? Does he or she just mean a bjection? What has continuity to do
with it? There's a whiff of "that's a nice sounding word, I'll use it"
here.
Like PO using words like "isomorphic" and "tautology" without any understanding of their technical meanings. That's possible...
It looks like you might be confusing "homomorphism" and "homeomorphism" though. God knows they deserve to be muddled! Who invents these names?
:)
(This aside, you point could still apply.)
I tried to make one major suggestion to the author: explain (in English)
in what way the core of the argument differs from the usual "it must
examine all the cases" non-proofs that keep cropping up.
And there's what I most unsure of. I've heard of these "examine all
cases" non-proofs, but I don't know what exactly makes them fail (is it
just that they don't give any reason why we must examine all the cases
or is it something deeper?)
On 29/09/2024 01:50, Keith Thompson wrote:
Ben Bacarisse <[email protected]> writes:... which reads to me as a "goodbye and good riddence!" note.
Mike Terry <[email protected]> writes:[...]
[...]It's funny - this group has had years and years of the likes of PO and his >>>> nonsense claims. It might seem almost like providence that just a couple >>>> of days after PO moves on (as it appears he has?)
I have been filtering his posts for some time, but now you mention it,
yes he's vanished. I fear he was telling the truth about his health and >>> he may be very ill now.
His most recent post was from Sep 21, 7 days ago, subject "Enough of
losers stuck in rebuttal mode", no body.
After all
the time posters have donated to PO, we might have hoped at least for a
more cheery "so long and thanks for all the fish", but I guess PO doesn't
see things that way. Anyway he's disappeared in the past for long periods (months) then finally returned, so we'll see.
On Sun, 29 Sep 2024 0:16:42 +0000, Ben Bacarisse wrote:
[email protected] (nnymous109) writes:
On Fri, 27 Sep 2024 22:42:31 +0000, Ben Bacarisse wrote:
Mike Terry <[email protected]> writes:
On 27/09/2024 00:34, Ben Bacarisse wrote:
[email protected] (nnymous109) writes:
Also, I did not know this yesterday, but alternatively, you can access >>>>>>> the document directly through the following link:I am hoping that this is a joke. If it is a joke, then I say well done >>>>>> sir (or madam)[*].
https://figshare.com/articles/preprint/On_Higher_Order_Recursions_25SEP2024/27106759?file=49414237
But I fear it is not a joke, in which case I have a problem with the >>>>>> first line. If you want two of the states to be symbols (and there are >>>>>> points later on that confirm that this is not a typo) then you need to >>>>>> explain why early on. You are free to define what you want, but a paper >>>>>> that starts "let 2 < 1" will have the reader wrong-footed from the >>>>>> start.
You mean q_accept and q_reject? It looks like they are just to
represent
the accept and reject states, not tape symbols? Calling them symbols is >>>>> like calling q_0 a symbol, which seems harmless to me - is it just that >>>>> you
want to call them "labels" or something other than "symbols"?
Later he/she writes
(Omega U {q_accept, q_reject})*
where * is, presumably, the Kleene closure. Omega is the set of
non-blank tape symbols of the TMs under discussion so these states are >>>> used to make "strings" with other tape symbols.
I agree that what the states actually are is irrelevant, but that two of >>>> them are later used like this is presumably important.
I don't fully get the notation though - e.g. it seems to me that the TMs >>>>> have tape symbols and states, but I don't see any state transition
table!
Right, but that's line 2 and I was starting at line 1!
I thought it might be joke because of the way the author just piles
definition on definition using bizarre notations like integral symbols >>>> but apparently not.
Okay, Ben. Please allow me to try again.
I'm not completely sure how to use USENET to reply to portions of
replies, so I will try to answer some of your queries here since the
other reply is much longer.
I didn't query anything here, did I? All my significant points were in
mt reply to you.
I don't actually use the Turing machines formalism at all in my
arguments until about point 22, so throughout the document I'm not
thinking about Turing machine states and Turing machine symbols and
Turing machine configurations, at all.
You don't use it in point 22 either. You use the words Turing and
machine but you don't use any TM formalism there.
But in trying to discuss with others, I tend to just cast the entire
argument in the language of Turing machines, since I felt that that
would be more familiar. Maybe I shouldn't have done that.
Your key audience (editors of prestigious journals) will be familiar
with every formalism. There's nothing to be gained by trying to make
the argument somehow familiar. Use whatever formalism best explains the
key points.
It's probably more accurate to say that I am trying to come up with a
string re-writing model of computation as you pick up on. So everything
is a string, and everything that can be used to form a string is a
symbol, so there's no semantic difference between the following strings: >>>
0 0 1 0 0 0 1
1 1 q_a r_e 0 0 2 3 d
q_accept q_reject q_accept 1 1 q_reject 0 0 0 d f g
Then we have some rules that tell us to replace substrings of any given
string with another string. That's the entire recursion idea (and yes,
we could do this with a Turing machine, but I'm asking us to forget
about Turing machines momentarily).
That's fine. No reader you care about should have any trouble with your
discussing string re-writing. They will all have trouble with the
points I made in my reply to you.
Also, rather than do a wall of text like last time, I think I should
pause and ask for criticisms here, and then answer them/proceed as is
necessary.
Okay, I have noted all that you have said. If there's something worth preserving in any of the ideas I have, I am perfectly happy to rewrite
these things using more idiomatic expressions.
With that introduction out of the way, we're right at the heart of the
thing. Given a string x and a recursion M, if y is the resultant string
upon the action of the recursion, we write M(x) = y.
If M(y) = z, then M(M(x)) = z, and equivalently M^2(x) = z.
Using S. as the integral symbol*, we let S.(M(x)) be the infinite tuple
<x, M(x), M^2(x), M^3(x), ...>.
We call S.(M(x)) the computation of x by M.
If U_M is the set of symbols over which M recurses over,
a property, P,
of M is a subset of U_M.
S.(M(x)) satisfies P if some substring of some
element of it is in P.
Writing [M] as an appropriate string representation of M and fixing a P,
we can define the set
L_P = {[M] such that there exists an x such that S.(M(x)) satisfies P}
With the assertion** that any recursion that decides that a
computation satisfies some property
With the assertion** that any recursion that decides that a
computation satisfies some property necessarily yields at least one
element of the computation***, I am suggesting that it is easier to
check for inclusion in this set that it is to check for exclusion.
** - I should have liked to call this a proof, but everything I come up
with ends up being circular, so I took the assertion on its face (which
kind of feels like cheating). Indeed, this is where I most need
validation.
And that's really the core of the idea. The definitions serve to handle
the technicalities that arise in the details, and to make sure that
existing concepts can be subsumed into the new scheme we have. If this
path doesn't sound promising, then it is unlikely that I have a proof
after all.
* - In my handwritten notes, I have this as some stylized left bracket.
I couldn't find what I was looking for when typing it out, so it became
the integral sign, but there's absolutely no relation with calculus.
*** - We can be even more restrictive with the assertion: the recursion necessarily yields at least some substring of at least one element of
the computation.
On Sun, 29 Sep 2024 23:19:02 +0000, Ben Bacarisse wrote:
Tuples are finite. S.(M(x)) is an infinite sequence.
Ok, noted. Is it that it is a tuple whenever it is finite, but when that constrained is relaxed and it is allowed to be a infinite, it is more appropriate to call it a sequence?
More terminology... This is usually referred to as iteration. The map M
is iterated to generate the sequence s_i = M^i(x).
I see. I shall use iterations instead.
I hope you say a lot about what M can be because, left open, the result
might not be what we would want to call a computation! Presumably, your
M is the function that maps one TM configuration to the next, yes?
Yes, provided you're interpreting something like 'q_0 1 1 1 0' that I
would a call a string as just a TM configuration.
I don't see why you say "recurses over". M is a map from strings to
strings. But using the term is merely a bit confusing. I don't think
you are trying to say anything significant by using it.
Okay, would 'iterates over' be better?
What I'm trying to get is say we have some string
G = 0 q z 1 0 1 and z is not in U_M,
M can still act on G in the following manner: if M contains a rule that
'0 q e' should be transformed into '1 1 q_b' where e is the empty
string,
M(G) = 1 1 q_b z 1 0 1
Weird, but OK. Substring seems to be rather weak, but maybe that's
important later on.
It allows us to extend things like halting.
It allows us to extend things like halting. Say I build M using the transition table of a Turing machine and at some point in the
computation, M^i(x) is 0 1 q_accept 1 1. Because we built M from a TM,
it will be the case that M^(i+1)(x) = M^i(x)
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.
With the assertion** that any recursion that decides that a
computation satisfies some property
What does that mean? So far we all we know is that a recursion (let's
call one R to save overusing the letter M) defines, for any string s, a
sequence R^i(s). What does it mean to say that R decides anything?
Explain what you mean with a simple trivial case. Don't jump right into
explaining what "decides that a computation satisfies some property"
means.
My guess: if a "recursion" is indeed the map from one TM configuration
to the next, then R decides membership of a set S like this:
s in S iff exists(i) such that R^i(s) = ...q_accept...
s not in S iff exists(i) such that R^i(s) = ...q_reject...
Is my guess right? If not, you need to say a lot more.
Okay, if I may re-render your guess using my terminology, we would have
s in S iff S.(R(s)) satisfies P1 = {q_accept}
s not in S iff S.(R(s)) satisfies P2 = {q_reject}
which is almost correct except for three points
1) We need to specify that the property satisfaction takes place after
the computation has become stationary.
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*.
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 [*]
So, to decide L_P,
Also, I did not know this yesterday, but alternatively, you can access
the document directly through the following link: https://figshare.com/articles/preprint/On_Higher_Order_Recursions_25SEP2024/27106759?file=49414237
[email protected] (nnymous109) writes:
Also, I did not know this yesterday, but alternatively, you can access
the document directly through the following link:
https://figshare.com/articles/preprint/On_Higher_Order_Recursions_25SEP2024/27106759?file=49414237
I am hoping that this is a joke. If it is a joke, then I say well done
sir (or madam)[*].
But I fear it is not a joke, in which case I have a problem with the
first line. If you want two of the states to be symbols (and there are points later on that confirm that this is not a typo) then you need to explain why early on. You are free to define what you want, but a paper
that starts "let 2 < 1" will have the reader wrong-footed from the
start.
[*] I once went to a contemporary art exhibition where the "catalogue"
was a set of "theorems" using real mathematical notations but it made no sense. It was fabulous.
On 27/09/2024 00:34, Ben Bacarisse wrote:
[email protected] (nnymous109) writes:
Also, I did not know this yesterday, but alternatively, you can accessI am hoping that this is a joke. If it is a joke, then I say well done
the document directly through the following link:
https://figshare.com/articles/preprint/On_Higher_Order_Recursions_25SEP2024/27106759?file=49414237
sir (or madam)[*].
But I fear it is not a joke, in which case I have a problem with the
first line. If you want two of the states to be symbols (and there are
points later on that confirm that this is not a typo) then you need to
explain why early on. You are free to define what you want, but a paper
that starts "let 2 < 1" will have the reader wrong-footed from the
start.
You mean q_accept and q_reject? It looks like they are just to represent
the accept and reject states, not tape symbols? Calling them symbols is
like calling q_0 a symbol, which seems harmless to me - is it just that you want to call them "labels" or something other than "symbols"?
I don't fully get the notation though - e.g. it seems to me that the TMs
have tape symbols and states, but I don't see any state transition
table!
On Thu, 26 Sep 2024 23:34:30 +0000, Ben Bacarisse wrote:
[email protected] (nnymous109) writes:
Also, I did not know this yesterday, but alternatively, you can access
the document directly through the following link:
https://figshare.com/articles/preprint/On_Higher_Order_Recursions_25SEP2024/27106759?file=49414237
I am hoping that this is a joke. If it is a joke, then I say well done
sir (or madam)[*].
But I fear it is not a joke, in which case I have a problem with the
first line. If you want two of the states to be symbols (and there are
points later on that confirm that this is not a typo) then you need to
explain why early on. You are free to define what you want, but a paper
that starts "let 2 < 1" will have the reader wrong-footed from the
start.
[*] I once went to a contemporary art exhibition where the "catalogue"
was a set of "theorems" using real mathematical notations but it made no
sense. It was fabulous.
Thank you for your reply and for considering the document.
In Mike Terry's words, I'm just using q_accept and q_reject as labels
(i.e., aside from where they are entered into the transition table, they aren't any different from 0 or 1). The reason I fix them beforehand is
that somewhere in the first construction I make, I want to have the
q_accept and q_reject of every machine be the same symbol.
I made a companion post on Reddit (but my replies are being blocked by
their spam filters), and I was told to give a general idea of what I was doing, so I provided the following:
-----
My strategy is to define a language over the string representations of
Turing machines.
A machine is then admitted into this language if there
is an input for which the machine assumes a certain configuration in the computation of that input.
The language is in NP because we can give some input as the certificate
of a machine. It is not in P because I'm arguing for some kind of independence between machine configurations, so that the verifier needs
to spit out all the configurations to assess them.
The verbosity (which I apologize for) comes from my attempts to make
precise these ideas, and to ensure some technicalities (like the
verifier always halting) hold.
-----
The reason I have this scheme of 'recursions' is because I was looking
for a natural way (at least, to me) to observe the configurations of
Turing machines. Say we have the machine's configuration (which doubles
as the input) as:
0 q_a 0 1 0 0 1 ....
where the first element beside the q_a is the current symbol scanned.
Say that symbol and state are updated, and the machine head moves to the right, the next configuration (and input for the second iteration)
becomes:
0 1 q_b 1 0 0 1 ....
But we can also see this as some substring of the previous configuration getting replaced with (transformed into) another string. That is, the substring '0 q_a 0' is replaced with '0 1 q_b'.
Now, q_a is a first-order symbol,
so the substring that was transformed
is only three symbols long. A second order symbol, r_b, could transform substrings seven symbols long, something like: '0 1 q_a r_b 0 1 1' to
'q_f 1 q_j r_c 0 0 1'. Notice that the second order symbols have 'power'
over all symbols with lower order: 1-order symbols (q_*), and 0-order
symbols (0 and 1).
The way I've imagined it: first the zero-order symbols do their thing
(they can only change substrings of length 1 [themselves], so if we
want
them fixed, we just have the iteration rules of the 0-order symbols be empty), then the first-order symbols do their own thing, and so on and
so forth, and we call the resulting process an iteration.
With this scheme, all sorts of things could now be valid inputs, e.g., q_accept q_reject 0 1 q_a 0 0 0, so things like standard strings, etc.,
are my way of identifying subsets of inputs that are relevant for the discussion at hand, e.g., strings like q_0 0 1 1 1 1 where q_0 is what
would ordinarily be an initial state are standard per q_0.
Now, I will bet that this scheme is too general for what we do with it
in the end (all of this is equivalent to some Turing machine, as I note
in 9), so the reason it's this way is two-fold:
First, when I started, I wasn't completely sure where I was headed and
what I would get in the end, and it just felt easier (at least at the
time) to think about it this way (the state is identified with the input
and with the configuration of the machine). Then we get to the end, and,
with the benefit of hindsight, I am pretty sure there is an easier path
to our final conclusion.
The second reason, and why I didn't just do a full re-write, is that I'm nursing dreams of one day doing work in Statistical Physics/Complex
Systems, and the scheme is reminiscent of that of cellular automata (to
my mind, at least). So, we have nice things (to my mind, again) like the iterations going on to infinity, except that at some point, the strings
don't change anymore, so there are very very faint ideas of some notion
of equilibrium that I would like to think some more about (probably
using a more general scheme).
But I suppose if you've somehow convinced (deluded?) yourself that
you've said something about P ?= NP, you ought to stop and tell someone
:)
Mike Terry <[email protected]> writes:
On 27/09/2024 00:34, Ben Bacarisse wrote:
[email protected] (nnymous109) writes:
Also, I did not know this yesterday, but alternatively, you can access >>>> the document directly through the following link:I am hoping that this is a joke. If it is a joke, then I say well done
https://figshare.com/articles/preprint/On_Higher_Order_Recursions_25SEP2024/27106759?file=49414237
sir (or madam)[*].
But I fear it is not a joke, in which case I have a problem with the
first line. If you want two of the states to be symbols (and there are
points later on that confirm that this is not a typo) then you need to
explain why early on. You are free to define what you want, but a paper >>> that starts "let 2 < 1" will have the reader wrong-footed from the
start.
You mean q_accept and q_reject? It looks like they are just to represent
the accept and reject states, not tape symbols? Calling them symbols is
like calling q_0 a symbol, which seems harmless to me - is it just that you >> want to call them "labels" or something other than "symbols"?
Later he/she writes
(Omega U {q_accept, q_reject})*
where * is, presumably, the Kleene closure. Omega is the set of
non-blank tape symbols of the TMs under discussion so these states are
used to make "strings" with other tape symbols.
I agree that what the states actually are is irrelevant, but that two of
them are later used like this is presumably important.
I don't fully get the notation though - e.g. it seems to me that the TMs
have tape symbols and states, but I don't see any state transition
table!
Right, but that's line 2 and I was starting at line 1!
I thought it might be joke because of the way the author just piles definition on definition using bizarre notations like integral symbols
but apparently not.
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.
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.
| Sysop: | Keyop |
|---|---|
| Location: | Huddersfield, West Yorkshire, UK |
| Users: | 715 |
| Nodes: | 16 (2 / 14) |
| Uptime: | 152:24:41 |
| Calls: | 12,091 |
| Calls today: | 4 |
| Files: | 15,000 |
| Messages: | 6,517,636 |