olcott <NoOne@NoWhere.com> writes:
The key missing piece in all of these dialogues is 100% perfectly and
exactly does it mean for a halt decider to compute the mapping from
its input finite strings to its own final states on the basis of the
actual behavior actually specified by this finite string pair.
You certainly have trouble understanding this so I will repeat my offer
to take you through a series of student exercises that I am confident (provided you approach them with an open mind) will lead you to fully understanding what this means.
olcott <NoOne@NoWhere.com> writes:
On 4/3/2022 5:07 PM, olcott wrote:
On 4/3/2022 4:56 PM, Ben Bacarisse wrote:
olcott <NoOne@NoWhere.com> writes:That depends on how you define your terms. Any element of the set of
On 4/3/2022 2:02 PM, Ben Bacarisse wrote:
olcott <NoOne@NoWhere.com> writes:
The key missing piece in all of these dialogues is 100% perfectly and >>>>>>> exactly does it mean for a halt decider to compute the mapping from >>>>>>> its input finite strings to its own final states on the basis of the >>>>>>> actual behavior actually specified by this finite string pair.You certainly have trouble understanding this so I will repeat my offer >>>>>> to take you through a series of student exercises that I am confident >>>>>> (provided you approach them with an open mind) will lead you to fully >>>>>> understanding what this means.
OK let's give it a shot.
Great! Let's start with something that will force a lot of hidden
assumptions to be made explicit.
Q: Is the set of even numbers decidable? If so, specify the TM (call it >>>> E) using Linz's notation (extended if you like). If not, why not?
(This may be slow to get started, because there is a lot low-level
things to iron out first.)
integers can be determined to be divisible by 2 with or without a remainder.
Can every element of this set be enumerated in finite time?
No. Can the set of all even numbers be defined in finite space?
Yes through algorithmic compression.
I forgot decidability is merely a membership algorithm, so yes.
(Didn't see you'd moved on. Ignore my last reply.)
I would say no. And for the reason you keep giving: any TM that decides membership can't have a number as input. TMs accept or reject strings,
not numbers.
But surely the iseven(n) function is computable, so how do you think we should resolve this? Hint: think encoding.
Can you have a stab at specifying E now using Linz's notation?
On Tuesday, 5 April 2022 at 06:32:34 UTC+8, olcott wrote:
On 4/4/2022 5:23 PM, wij wrote:
On Tuesday, 5 April 2022 at 04:47:42 UTC+8, olcott wrote:My analysis is based on this model: If "an X is a Y" and Z says that "an
On 4/4/2022 3:36 PM, olcott wrote:
On 4/4/2022 2:51 PM, Ben Bacarisse wrote:The process that we are doing looks like it will be effective on the
olcott <No...@NoWhere.com> writes:
On 4/4/2022 11:23 AM, Ben Bacarisse wrote:
olcott <No...@NoWhere.com> writes:
On 4/4/2022 10:32 AM, Ben Bacarisse wrote:Yes, that good. You didn't.
olcott <No...@NoWhere.com> writes:You told me to make sure that I do not provide an algorithm.
On 4/4/2022 5:14 AM, Ben Bacarisse wrote:We've hit a bit of a road-block rather sooner that I had expected. >>>>>>>>>> First off, there's no need to define what a prime number is. If >>>>>>>>>> at some
olcott <No...@NoWhere.com> writes:
On 4/3/2022 8:14 PM, Ben Bacarisse wrote:That's getting close. We know, from how the notation works, >>>>>>>>>>>> that S is a
It might be time to skip ahead because the next exercise is to >>>>>>>>>>>>>> do the
same for P, a TM that decides if a string encodes a prime >>>>>>>>>>>>>> number. Can
you think of how to specify that without giving an algorithm? >>>>>>>>>>>>>> P.q0 ??? ⊦* P.qy if ???
P.q0 ??? ⊦* P.qn otherwise.
(The three ??? won't all be the same things.) Any idea how to >>>>>>>>>>>>>> flesh
this out? If you can, you will be able to do it for E very >>>>>>>>>>>>>> easily too.
P.q0 S ⊦* P.qy if Is-Prime-Number(S)
P.q0 S ⊦* P.qn otherwise.
string of symbols in the TM's alphabet. But writing
Is-Prime-Number(S)
suggests that is not natural language. That's a very hard route >>>>>>>>>>>> to go
down. I'd have to ask you for the definition of Is-Prime-Number. >>>>>>>>>>>> Defining it symbolically is messy and if the definition is /not/ >>>>>>>>>>>> formal,
dressing the definition up with a formal-looking name is just >>>>>>>>>>>> superficial.
It goes through some tedious steps to see if it is a prime number: >>>>>>>>>>>
A prime number is a natural number greater than 1 that is not a >>>>>>>>>>> product of two smaller natural numbers.
point it turns out that your readers do not know, go ahead and define
it, but it's too widely understood by comp.theory readers to bother >>>>>>>>>> about.
But writing (as I think you are suggesting)
P.q0 S ⊦* P.qy it goes through some tedious steps to see >>>>>>>>>> if it is a
prime number
is not really adequate. There are two 'it'. To what do they refer? >>>>>>>>>
Now, to what do the two 'it's refer?
OK, maybe things have gone too far already, but why are you ignoring my >>>>>> questions? Your phrase used 'it' twice. What did you intend to refer >>>>>> to by these two pronouns? It was not an idle question. I think when >>>>>> you answer it, at least one problem will become clear.
This is somewhat algorithmic:No, no. The non-algorithmic way is best. You should be able to >>>>>>>> specific what a computation does even when yo have no idea how to write
the an algorithm to do it. Sometimes there isn't ad algorithm! >>>>>>>>
didn't answer any of them. This will only work if you try to answer >>>>>>>> these questions. Sometimes the answer will be "I don't know what you >>>>>>>> mean", but that's a perfectly good answer.and nothing in P.q0 S ⊦* P.qy is a number so there is nothing >>>>>>>>>> there to
be a prime number.
Can you see how you (a) make it shorter, (b) make it clearer? >>>>>>>> My reply has three questions in it (depending on how you count) but you
Anything besides the bare function name is somewhat algorithmic so >>>>>>> what you are asking for seems impossible.
Here's a supporting exercise. Write down at least half a dozen strings >>>>>> that might be passed to P. At least one of them should be a string that >>>>>> P must accept and at least one must be a string the P should reject, but >>>>>> you should say, for each one, whether P accepts of rejects it.
Be prepared for me to raise questions about what the strings represent. >>>>>> It's easy to assume conventions from everyday life that should be stated >>>>>> explicitly. You must have come across this in software: "the manual >>>>>> said the input should be a number but it went wrong for सहस्र."
Finally, don't fuss about the prime bit. Just use the word prime.
Everyone one knows what it means. The key thing here is to state /what/ >>>>>> must be prime for P to correctly accept a string.
I am estimating that we will finally achieve closure on this.
Creating a common language between us will achieve the basis for mutual >>>>> understanding.
basis of eliminating all hidden assumptions.
--
Copyright 2022 Pete Olcott
"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer
No use. Even all the people you find agree with you is still useless. To claim
you solved the HP problem, you have to show ALL your H first. People cannot >>> judge or teach 'claims'. But your P already showed wrong, no need to publish H.
X is a Y" then anything in the universe that disagrees is necessarily
incorrect.
"an X is a Y" =
The input to embedded_H specifies a non-halting sequence of
configurations. (input is non-halting)
Z says that "an X is a Y" =
embedded_H rejects its input.
If you can think of a case where
"an X is a Y" is simultaneously true and false then you have a rebuttal,
otherwise not so much.
--
Copyright 2022 Pete Olcott
"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer
You simply do not have H. What you say? If you say yes, then show it to prove.
On Tuesday, 5 April 2022 at 04:47:42 UTC+8, olcott wrote:
On 4/4/2022 3:36 PM, olcott wrote:
On 4/4/2022 2:51 PM, Ben Bacarisse wrote:The process that we are doing looks like it will be effective on the
olcott <No...@NoWhere.com> writes:
On 4/4/2022 11:23 AM, Ben Bacarisse wrote:
olcott <No...@NoWhere.com> writes:
On 4/4/2022 10:32 AM, Ben Bacarisse wrote:Yes, that good. You didn't.
olcott <No...@NoWhere.com> writes:You told me to make sure that I do not provide an algorithm.
On 4/4/2022 5:14 AM, Ben Bacarisse wrote:We've hit a bit of a road-block rather sooner that I had expected. >>>>>>>> First off, there's no need to define what a prime number is. If >>>>>>>> at some
olcott <No...@NoWhere.com> writes:
On 4/3/2022 8:14 PM, Ben Bacarisse wrote:That's getting close. We know, from how the notation works, >>>>>>>>>> that S is a
It might be time to skip ahead because the next exercise is to >>>>>>>>>>>> do the
same for P, a TM that decides if a string encodes a prime >>>>>>>>>>>> number. Can
you think of how to specify that without giving an algorithm? >>>>>>>>>>>> P.q0 ??? ⊦* P.qy if ???
P.q0 ??? ⊦* P.qn otherwise.
(The three ??? won't all be the same things.) Any idea how to >>>>>>>>>>>> flesh
this out? If you can, you will be able to do it for E very >>>>>>>>>>>> easily too.
P.q0 S ⊦* P.qy if Is-Prime-Number(S)
P.q0 S ⊦* P.qn otherwise.
string of symbols in the TM's alphabet. But writing
Is-Prime-Number(S)
suggests that is not natural language. That's a very hard route >>>>>>>>>> to go
down. I'd have to ask you for the definition of Is-Prime-Number. >>>>>>>>>> Defining it symbolically is messy and if the definition is /not/ >>>>>>>>>> formal,
dressing the definition up with a formal-looking name is just >>>>>>>>>> superficial.
It goes through some tedious steps to see if it is a prime number: >>>>>>>>>
A prime number is a natural number greater than 1 that is not a >>>>>>>>> product of two smaller natural numbers.
point it turns out that your readers do not know, go ahead and define >>>>>>>> it, but it's too widely understood by comp.theory readers to bother >>>>>>>> about.
But writing (as I think you are suggesting)
P.q0 S ⊦* P.qy it goes through some tedious steps to see >>>>>>>> if it is a
prime number
is not really adequate. There are two 'it'. To what do they refer? >>>>>>>
Now, to what do the two 'it's refer?
OK, maybe things have gone too far already, but why are you ignoring my >>>> questions? Your phrase used 'it' twice. What did you intend to refer >>>> to by these two pronouns? It was not an idle question. I think when
you answer it, at least one problem will become clear.
This is somewhat algorithmic:No, no. The non-algorithmic way is best. You should be able to
specific what a computation does even when yo have no idea how to write >>>>>> the an algorithm to do it. Sometimes there isn't ad algorithm!
My reply has three questions in it (depending on how you count) but you >>>>>> didn't answer any of them. This will only work if you try to answer >>>>>> these questions. Sometimes the answer will be "I don't know what you >>>>>> mean", but that's a perfectly good answer.and nothing in P.q0 S ⊦* P.qy is a number so there is nothing >>>>>>>> there to
be a prime number.
Can you see how you (a) make it shorter, (b) make it clearer?
Anything besides the bare function name is somewhat algorithmic so
what you are asking for seems impossible.
Here's a supporting exercise. Write down at least half a dozen strings >>>> that might be passed to P. At least one of them should be a string that >>>> P must accept and at least one must be a string the P should reject, but >>>> you should say, for each one, whether P accepts of rejects it.
Be prepared for me to raise questions about what the strings represent. >>>> It's easy to assume conventions from everyday life that should be stated >>>> explicitly. You must have come across this in software: "the manual
said the input should be a number but it went wrong for सहस्र." >>>>
Finally, don't fuss about the prime bit. Just use the word prime.
Everyone one knows what it means. The key thing here is to state /what/ >>>> must be prime for P to correctly accept a string.
I am estimating that we will finally achieve closure on this.
Creating a common language between us will achieve the basis for mutual
understanding.
basis of eliminating all hidden assumptions.
--
Copyright 2022 Pete Olcott
"Talent hits a target no one else can hit;
Genius hits a target no one else can see."
Arthur Schopenhauer
No use. Even all the people you find agree with you is still useless. To claim
you solved the HP problem, you have to show ALL your H first. People cannot judge or teach 'claims'. But your P already showed wrong, no need to publish H.
On 04/04/2022 14:28, Ben Bacarisse wrote:
[I wrote:]
The reasons why it's not possible to write a halt decider showNow here there is technical wrinkle. One can, probably, prove that
up perfectly well if you try to do so in K&R C for a PDP 11 [64K bytes
code, same for date, 2.4M discs, ...]. They're not things that can
only be done with supercomputers with hundreds of processors, etc.
These interminable threads get hung up on the behaviour of programs of
less than a page of code.
halting of bounded-resource computations can't be solved by certain
similarly bounded-resource machines. But who'd want to do the maths to
prove that? And if the decider has unbounded resources, then halting of
bounded-resource computations /is/ decidable -- trivially so.
Yes, but I was thinking of real, skilled, programmers trying to do the manifestly impossible. I have in mind one of our [successful!] MSc students who visited two or three years later: "What are you doing?" "Oh, my boss got fed up with [programs that something-or-other, I forget what],
so he wanted me to write a program that detects [whatever-it-was]." "But that's not possible, it's a simple reduction from the HP!" "Oh, no, I've almost done it, just a couple of cases to sort out." A few months later,
he came by again: "Sorted those, but there are a few bugs." "Hm, well, good luck, but I still think it's impossible." A few months again, and
I got a letter [these were the days before e-mail!] -- "You were right!
It could do the toy examples I gave it, but it got stuck with any real programs, and I can't make progress, so we've given up."
PO's problems with his "fully coded TMs" aren't caused by his PC being finite, nor by limitations of C or his OS, nor even [as far as we
know] by bugs in his "emulator", but by his failures to understand what
the HP is really about, and his failures to produce a proper "hatted"
version of his attempts to solve it.
When trying to get PO to see how to specify a computation, I don't want
to deal with all the distractions that using some abstract C with no
pointer limitations will throw up.
Instead, you're having to deal with his apparent [but he may just
be trolling] difficulties in understanding what you want. I wonder how he would get on with similar exercises in C, where he's not struggling with
the concept of unary [and efficiency] but could simply count and perhaps analyse characters in the standard input? [FTAOD, "wonder" is something
of an exaggeration.]
On 2022-04-05 15:02, olcott wrote:
On 4/5/2022 3:57 PM, André G. Isaak wrote:
On 2022-04-05 11:07, olcott wrote:
On 4/5/2022 9:40 AM, Ben Bacarisse wrote:
olcott <NoOne@NoWhere.com> writes:
On 4/4/2022 7:57 PM, Ben Bacarisse wrote:
Aside: TMs are often specified to operate on numbers in unary
notation
because it is so simple.
The notation is simple making the algorithm more complex.
No. This exercise will help you see why that is not true:
Write a TM that adds two numbers. The input will be strings of the >>>>> form {n}+{m} where {x} is the unary representation of x. The TM >>>>> should halt with only {n+m} on the tape.
Now do the same where the numbers are represented in the usual
decimal
notation.
I was referring to the difference between binary and unary.
Then why not construct a TM that does this using unary notation and
one that does it using binary notation? You'll find the former is
much simpler.
André
Unary freaks me out with its counter-intuitive nature. Ben says that
it proves to be simpler than binary and I accept his word on this.
But don't you think that it would be worth your while to try to
understand *why* this is the case?
One of Ben's goals seems to be to get you to actually construct a Turing Machine, a task which would almost certainly rid you of many of your misconceptions about Turing Machines and how they work.
His example of an "Eveness Decider" is trivial to construct regardless
of whether you use unary or binary representation (though it is slightly easier using the former). This example is "Hello World!" territory, not
some massive undertaking. You'd really benefit from actually attempting
this.
André
On 2022-04-05 17:49, olcott wrote:
On 4/5/2022 6:39 PM, André G. Isaak wrote:
On 2022-04-05 17:31, olcott wrote:
On 4/5/2022 6:25 PM, André G. Isaak wrote:
On 2022-04-05 17:05, olcott wrote:
On 4/5/2022 5:32 PM, Jeff Barnett wrote:
On 4/5/2022 3:33 PM, olcott wrote:
On 4/5/2022 4:24 PM, André G. Isaak wrote:
On 2022-04-05 15:02, olcott wrote:
On 4/5/2022 3:57 PM, André G. Isaak wrote:
On 2022-04-05 11:07, olcott wrote:
On 4/5/2022 9:40 AM, Ben Bacarisse wrote:Then why not construct a TM that does this using unary
olcott <NoOne@NoWhere.com> writes:
On 4/4/2022 7:57 PM, Ben Bacarisse wrote:
No. This exercise will help you see why that is not true: >>>>>>>>>>>>>Aside: TMs are often specified to operate on numbers in >>>>>>>>>>>>>>> unary notation
because it is so simple.
The notation is simple making the algorithm more complex. >>>>>>>>>>>>>
Write a TM that adds two numbers. The input will be >>>>>>>>>>>>> strings of the
form {n}+{m} where {x} is the unary representation of x. >>>>>>>>>>>>> The TM
should halt with only {n+m} on the tape.
Now do the same where the numbers are represented in the >>>>>>>>>>>>> usual decimal
notation.
I was referring to the difference between binary and unary. >>>>>>>>>>>
notation and one that does it using binary notation? You'll >>>>>>>>>>> find the former is much simpler.
And while you are at it, try base three numbers (or any odd base >>>>>>> greater than one). But no matter what, try writing a TM. Lose
your fear of public failure and dive in somewhere.
It is not a fear of failure nitwit.
It is like asking a brain surgeon do you know what a bed pan is?
Except that you have consistently demonstrated that you *don't*
have even the vaguest understanding of how TMs work, so the above
analogy is hardly apropos.
The most direct path forward on this might be to implement a
base-2 even-number decider in this system:
http://www.lns.mit.edu/~dsw/turing/turing.html
(a) Go to the end of the input (space delimited)
(b) Test last input tape cell for "0" digit
(c) Accept or Reject input.
So why not just demonstrate how this works by constructing the
actual TM?
It is self-evident that I know exactly how this works by my
specification.
What you give above is not a specification. A specification is what
Ben has been asking you to provide but which you have been unable or
unwilling to do.
If neither of you can see how the above would be translated into a TM of
this kind: http://www.lns.mit.edu/~dsw/turing/turing.html
You are not too bright.
The task I suggested for you was to construct both an evenness-decider
that uses binary representations and one that uses unary representations
so you could see why the latter is simpler. Giving an outline of a
single algorithm without actually constructing the two Turing Machines
is not going to achieve that. As I said, these TMs are of the "Hello
World!" level of difficulty, so your reluctance is a bit mystifying.
André
Andy Walker <anw@cuboid.co.uk> writes:
On 06/04/2022 02:57, Ben Bacarisse wrote:
[I wrote:]
Yes, but I was thinking of real, skilled, programmers trying to do
the manifestly impossible. I have in mind one of our [successful!] MSc >>>> students who visited two or three years later: [...].
What used to be called a "conversion MSc"?
Yes, and no. We didn't think of it that way, as we treated CS
as just another branch of maths -- all of our students did some, just
as they all did some statistics, and quite a lot chose to do CS options
in the third year. From that PoV, it was a continuation rather than a
conversion MSc, offering more advanced CS [and statistics, ...] than
had been in the BSc. But it could have been a conversion for students
coming with [maths] BScs from other places.
Ours was more genuinely conversion as we took students with, in theory,
any background at all -- philosophy, English, history, whatever. In
general those with maths, physics and EE backgrounds has fewer problems,
but the MSc (in contrast to the BSc) was deliberately designed to have
less theory in it.
[...]
Instead, you're having to deal with his apparent [but he may justRight. I think TMs may be a step too far. I don't think I'll get even
be trolling] difficulties in understanding what you want. I wonder how he >>>> would get on with similar exercises in C, [...].
one TM accurately specified, let alone written.
You [and others] know this, yet persist! I suppose there is
some interest in knowing what the next wriggle will be?
I just wonder when he'll stop the "tutorial".
As for the main mistake, I know enough about cranks to aim for only one
of two things: can they be persuaded to say enough to show others that
they are wrong (for example PO admission that H(P,P) == false is correct despite the fact that P(P) halts),
On Wednesday, April 6, 2022 at 11:29:06 AM UTC-4, olcott wrote:halts, which is the actual question *as stated in the Linz proof*.
On 4/6/2022 9:19 AM, Ben Bacarisse wrote:
Andy Walker <a...@cuboid.co.uk> writes:If it is the case that the simulated input to H cannot possibly reach
On 06/04/2022 02:57, Ben Bacarisse wrote:
[I wrote:]
Yes, but I was thinking of real, skilled, programmers trying to do >>>>>> the manifestly impossible. I have in mind one of our [successful!] MSc >>>>>> students who visited two or three years later: [...].
What used to be called a "conversion MSc"?
Yes, and no. We didn't think of it that way, as we treated CS
as just another branch of maths -- all of our students did some, just
as they all did some statistics, and quite a lot chose to do CS options >>>> in the third year. From that PoV, it was a continuation rather than a
conversion MSc, offering more advanced CS [and statistics, ...] than
had been in the BSc. But it could have been a conversion for students
coming with [maths] BScs from other places.
Ours was more genuinely conversion as we took students with, in theory,
any background at all -- philosophy, English, history, whatever. In
general those with maths, physics and EE backgrounds has fewer problems, >>> but the MSc (in contrast to the BSc) was deliberately designed to have
less theory in it.
[...]
Instead, you're having to deal with his apparent [but he may justRight. I think TMs may be a step too far. I don't think I'll get even >>>>> one TM accurately specified, let alone written.
be trolling] difficulties in understanding what you want. I wonder how he
would get on with similar exercises in C, [...].
You [and others] know this, yet persist! I suppose there is
some interest in knowing what the next wriggle will be?
I just wonder when he'll stop the "tutorial".
As for the main mistake, I know enough about cranks to aim for only one
of two things: can they be persuaded to say enough to show others that
they are wrong (for example PO admission that H(P,P) == false is correct >>> despite the fact that P(P) halts),
its own final state under any condition what-so-ever then H correctly
maps this finite string input to its reject state and nothing in the
universe can correctly contradict that H is correct.
If you have a white dog in your living room and everyone in the universe
disagrees, you still have a white dog in your living room.
What you've actually shown is that for any simulating halt decider H, H^ built from it, and input <H^><H^> which represents H^ applied to <H^>, no H can simulate H^ applied to <H^> to its final state. This says nothing of whether H^ applied to <H^>
If it is the case that the
simulated input to H cannot possibly reach
its own final state under any condition what-so-ever then
H correctly
maps this finite string input to its reject state and nothing in the
universe can correctly contradict that H is correct.
You may in fact have a white dog in your living room, and people do agree with that, but no one cares because they want to know if there is a black cat in your kitchen.
On Wednesday, April 6, 2022 at 1:49:43 PM UTC-4, olcott wrote:halts, which is the actual question *as stated in the Linz proof*.
On 4/6/2022 12:07 PM, Dennis Bush wrote:
On Wednesday, April 6, 2022 at 12:59:15 PM UTC-4, olcott wrote:
On 4/6/2022 11:43 AM, Dennis Bush wrote:
On Wednesday, April 6, 2022 at 11:29:06 AM UTC-4, olcott wrote:
On 4/6/2022 9:19 AM, Ben Bacarisse wrote:
Andy Walker <a...@cuboid.co.uk> writes:If it is the case that the simulated input to H cannot possibly reach >>>>>> its own final state under any condition what-so-ever then H correctly >>>>>> maps this finite string input to its reject state and nothing in the >>>>>> universe can correctly contradict that H is correct.
On 06/04/2022 02:57, Ben Bacarisse wrote:
[I wrote:]
Yes, but I was thinking of real, skilled, programmers trying to do >>>>>>>>>> the manifestly impossible. I have in mind one of our [successful!] MSc
students who visited two or three years later: [...].
What used to be called a "conversion MSc"?
Yes, and no. We didn't think of it that way, as we treated CS
as just another branch of maths -- all of our students did some, just >>>>>>>> as they all did some statistics, and quite a lot chose to do CS options
in the third year. From that PoV, it was a continuation rather than a >>>>>>>> conversion MSc, offering more advanced CS [and statistics, ...] than >>>>>>>> had been in the BSc. But it could have been a conversion for students >>>>>>>> coming with [maths] BScs from other places.
Ours was more genuinely conversion as we took students with, in theory, >>>>>>> any background at all -- philosophy, English, history, whatever. In >>>>>>> general those with maths, physics and EE backgrounds has fewer problems,
but the MSc (in contrast to the BSc) was deliberately designed to have >>>>>>> less theory in it.
[...]
Instead, you're having to deal with his apparent [but he may just >>>>>>>>>> be trolling] difficulties in understanding what you want. I wonder how heRight. I think TMs may be a step too far. I don't think I'll get even >>>>>>>>> one TM accurately specified, let alone written.
would get on with similar exercises in C, [...].
You [and others] know this, yet persist! I suppose there is
some interest in knowing what the next wriggle will be?
I just wonder when he'll stop the "tutorial".
As for the main mistake, I know enough about cranks to aim for only one >>>>>>> of two things: can they be persuaded to say enough to show others that >>>>>>> they are wrong (for example PO admission that H(P,P) == false is correct
despite the fact that P(P) halts),
If you have a white dog in your living room and everyone in the universe >>>>>> disagrees, you still have a white dog in your living room.
What you've actually shown is that for any simulating halt decider H, H^ built from it, and input <H^><H^> which represents H^ applied to <H^>, no H can simulate H^ applied to <H^> to its final state. This says nothing of whether H^ applied to <H^>
Ĥ applied to ⟨Ĥ⟩ specifies a different sequence of configurations than >> the simulation of ⟨Ĥ⟩ ⟨Ĥ⟩ by embedded_H.CORRECTLY
If it is the case that the
computation that halts … the Turing machine will halt whenever it enters >>>> a final state. (Linz:1990:234) cannot possibly be met thereforesimulated input to H cannot possibly reach
its own final state under any condition what-so-ever then
The *turing machine*, not an inaccurate simulation. The measurement of correct is what H^ applied to <H^> does.
Then you're answering the wrong question. The question being asked is "Does H^ applied to <H^> halt?",
On Wednesday, April 6, 2022 at 2:05:36 PM UTC-4, olcott wrote:
On 4/6/2022 12:55 PM, Dennis Bush wrote:halts, which is the actual question *as stated in the Linz proof*.
On Wednesday, April 6, 2022 at 1:49:43 PM UTC-4, olcott wrote:
On 4/6/2022 12:07 PM, Dennis Bush wrote:
On Wednesday, April 6, 2022 at 12:59:15 PM UTC-4, olcott wrote:
On 4/6/2022 11:43 AM, Dennis Bush wrote:
On Wednesday, April 6, 2022 at 11:29:06 AM UTC-4, olcott wrote: >>>>>>>> On 4/6/2022 9:19 AM, Ben Bacarisse wrote:
Andy Walker <a...@cuboid.co.uk> writes:If it is the case that the simulated input to H cannot possibly reach >>>>>>>> its own final state under any condition what-so-ever then H correctly >>>>>>>> maps this finite string input to its reject state and nothing in the >>>>>>>> universe can correctly contradict that H is correct.
On 06/04/2022 02:57, Ben Bacarisse wrote:
[I wrote:]
Yes, but I was thinking of real, skilled, programmers trying to do >>>>>>>>>>>> the manifestly impossible. I have in mind one of our [successful!] MSc
students who visited two or three years later: [...].
What used to be called a "conversion MSc"?
Yes, and no. We didn't think of it that way, as we treated CS >>>>>>>>>> as just another branch of maths -- all of our students did some, just
as they all did some statistics, and quite a lot chose to do CS options
in the third year. From that PoV, it was a continuation rather than a
conversion MSc, offering more advanced CS [and statistics, ...] than >>>>>>>>>> had been in the BSc. But it could have been a conversion for students
coming with [maths] BScs from other places.
Ours was more genuinely conversion as we took students with, in theory,
any background at all -- philosophy, English, history, whatever. In >>>>>>>>> general those with maths, physics and EE backgrounds has fewer problems,
but the MSc (in contrast to the BSc) was deliberately designed to have
less theory in it.
[...]
Instead, you're having to deal with his apparent [but he may just >>>>>>>>>>>> be trolling] difficulties in understanding what you want. I wonder how heRight. I think TMs may be a step too far. I don't think I'll get even
would get on with similar exercises in C, [...].
one TM accurately specified, let alone written.
You [and others] know this, yet persist! I suppose there is >>>>>>>>>> some interest in knowing what the next wriggle will be?
I just wonder when he'll stop the "tutorial".
As for the main mistake, I know enough about cranks to aim for only one
of two things: can they be persuaded to say enough to show others that
they are wrong (for example PO admission that H(P,P) == false is correct
despite the fact that P(P) halts),
If you have a white dog in your living room and everyone in the universe
disagrees, you still have a white dog in your living room.
What you've actually shown is that for any simulating halt decider H, H^ built from it, and input <H^><H^> which represents H^ applied to <H^>, no H can simulate H^ applied to <H^> to its final state. This says nothing of whether H^ applied to <H^
No that is not the freaking question you freaking nitwit.Ĥ applied to ⟨Ĥ⟩ specifies a different sequence of configurations thanCORRECTLY
If it is the case that the
computation that halts … the Turing machine will halt whenever it enterssimulated input to H cannot possibly reach
its own final state under any condition what-so-ever then
a final state. (Linz:1990:234) cannot possibly be met therefore
The *turing machine*, not an inaccurate simulation. The measurement of correct is what H^ applied to <H^> does.
the simulation of ⟨Ĥ⟩ ⟨Ĥ⟩ by embedded_H.
Then you're answering the wrong question. The question being asked is "Does H^ applied to <H^> halt?",
The question is: Does the input specify a sequence of configurations
that would reach their own final state?
FALSE. From Linz:
On Wednesday, April 6, 2022 at 2:56:33 PM UTC-4, olcott wrote:
On 4/6/2022 1:49 PM, Ben Bacarisse wrote:
olcott <No...@NoWhere.com> writes:We have to get to the point where you understand that I aleady know this
I thought you wanted to learn how TMs are
specified so you had the knowledge to read and understand Linz's
specifications.
Not at all. I already understand this better than you do.
Ah, let's call it a day then.
better than you so I am willing to proceed with the E TM.
Bold words from someone who can't write what's effectively a "hello world" TM.
On Wednesday, April 6, 2022 at 10:55:06 PM UTC-4, olcott wrote:
On 4/6/2022 9:45 PM, Dennis Bush wrote:
On Wednesday, April 6, 2022 at 10:40:15 PM UTC-4, olcott wrote:The actual sequence of configurations specified by these three is not
On 4/6/2022 9:26 PM, Dennis Bush wrote:
On Wednesday, April 6, 2022 at 10:15:18 PM UTC-4, olcott wrote:It represents a sequence of configurations.
On 4/6/2022 9:12 PM, Dennis Bush wrote:
On Wednesday, April 6, 2022 at 10:10:45 PM UTC-4, olcott wrote: >>>>>>>> On 4/6/2022 9:03 PM, André G. Isaak wrote:Yes.
On 2022-04-06 19:47, olcott wrote:The all has to do with mathematicaly fomrmalizing semantic meanings. >>>>>>>> Finite strings can have semantic properties.
On 4/6/2022 8:41 PM, André G. Isaak wrote:Not by any normal definition.
On 2022-04-06 19:25, olcott wrote:
On 4/6/2022 8:17 PM, André G. Isaak wrote:
On 2022-04-06 19:10, olcott wrote:
On 4/6/2022 7:50 PM, André G. Isaak wrote:
But, now that we've got that out of the way, here's a simple >>>>>>>>>>>>>>> question for you: If you want your evenness decider to decide >>>>>>>>>>>>>>> whether seven is even, which string would you pass to it? [yes, I
know this is trivially obvious, just humour me]
André
111[]
I'm assuming that you're using [] to indicate a blank. >>>>>>>>>>>>>
Presumably your E would *reject* this string since seven is an odd
number rather than an even one.
But notice that in the above case your Turing Machine is rejecting
a finite string "111␣" based on the fact that the *integer* seven,
which is neither an input nor a finite string, is not even. >>>>>>>>>>>>>
So your decider is mapping from a finite string (its input) to >>>>>>>>>>>>> reject/accept based on something which is a "non-input non-finite >>>>>>>>>>>>> string" (to use an expression you've often used).
That seems totally incoherent.
The TM maps its input finite string to its reject state based on a >>>>>>>>>>>> property of this finite string.
But 'evenness' is not a property of strings; it is a property of >>>>>>>>>>> numbers, and strings are not numbers.
It can be correctly construed as the property of the string. >>>>>>>>>
A string is an *uninterpreted* sequence of symbols.
Your decider bases its decision on a property of the string (is the >>>>>>>>>>> final digit 0?), but that property only corresponds to evenness by >>>>>>>>>>> virtue of the encoding you have chosen.
A decider which uses a unary representation (which would be slightly
simpler than your binary one) couldn't just look at a single digit. Nor
Thus not actually simpler.
If you actually attempted to write the two versions of E, you'd discover
that you are simply wrong in this assessment. The fact that you don't >>>>>>>>> realize this is merely a testament to the fact that you really don't >>>>>>>>> understand how Turing Machines work. At all.
could one that used trinary representation (which would be only >>>>>>>>>>> slightly more complex than your binary one).
What makes all three of these valid evenness deciders is that they >>>>>>>>>>> conform to the specification of an evenness decider:
E.q0 S ⊦* E.qy if the *number* represented by the string S is even
E.q0 S ⊦* E.qn otherwise.
Yes, the TM maps a finite string to an accept/reject state, but this
mapping is based on the property of the *number* which that string >>>>>>>>>>> encodes. That number is not an input, but because it can be encoded >>>>>>>>>>> as a string we can still legitimately expect a Turing Machine to >>>>>>>>>>> answer questions about that number.
It can be construed as a property of the string.
No. It cannot be. Properties of a string would include things like >>>>>>>>> 'length', 'number of distinct symbols', 'is it a palindrome?', etc. >>>>>>>>> Evenness is not one of those properties.
Talking about a finite string as being even or odd is completely >>>>>>>>>>> meaningless. Only numbers can be even or odd. Yet there is no problem
in constructing such a decider.
The string has the "even binary integer" property.
No. As soon as you start assigning numerical values to a string (or even
to the individual symbols of a string) you are no longer treating it >>>>>>>>> purely as a string. You are considering the information which is encoded
in that string, which is a separate matter.
And just like the meaning assigned to the string "111␣" is the number 7, the meaning assigned to the string <H^><H^> is the turing machine H^ applied to <H^>.
Ah, so you're finally agreeing that the input <H^><H^> represents H^ applied to <H^>, and that therefore H applied to <H^><H^> is supposed determine if H^ applied to <H^> halts?
And that sequence of configurations is H^ applied to <H^> as per the stipulative definition of a halt decider:
the same thus the behavior can vary.
H ⟨Ĥ⟩ ⟨Ĥ⟩
Ĥ ⟨Ĥ⟩
embedded_H ⟨Ĥ⟩ ⟨Ĥ⟩
You can simply assume that they must be the same, yet when you list them
you can see that they are not the same.
By definition the input to H and embedded_H is the representation of Ĥ ⟨Ĥ⟩
Sysop: | Keyop |
---|---|
Location: | Huddersfield, West Yorkshire, UK |
Users: | 365 |
Nodes: | 16 (2 / 14) |
Uptime: | 24:50:37 |
Calls: | 7,769 |
Files: | 12,905 |
Messages: | 5,749,272 |