Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss
Re: The answer to the Halting Problem stored within Permutations of Internal States?
27 views
Skip to first unread message
Graham Cooper
May 17, 2012, 2:04:47 AM5/17/12
to
On May 14, 6:30 am, Chris Menzel <cmen...@remove-this.tamu.edu> wrote:
> On Sun, 13 May 2012 10:15:08 -0500, Peter Olcott <OCR4Screen> said:
>
> > The Halting Problem proposes that it will always be impossible to
> > create a halting decider.
>
> The Halting Problem "proposes" no such thing. The Halting Problem is
> simply the problem of whether such a decider (in the form of a Turing
> machine, program, recursive function, what have you) exists. And as
> Turing himself proved, the answer is No. End of story (though of course
> the story is well worth learning).
The Halting Problem combined with the Church Turing Thesis does
suggest exactly that!
i.e. CTT = no new computational system can be more advanced than a
single TM
The Halting Problem may be solvable.
The problem is: Both the Godel Proof and Halting Proof are "copouts"!
"We can't program the function!", but we can formulate why we can't
find the solution instead!
The Godel proof begins...
Assume a PROOF() Predicate exists that inputs a theorem (GODEL NUMBER)
and outputs TRUE IFF a sequence of theorems in the theory conclude
with the final line equal to the input theorem under question.
i.e. a proof of the theorem exists by enumerable axiomatic modus
ponens.
The Proof concludes such a PROOF() Predicate doesn't exist!
Wait! Here it is!
PROOF(C) = C v (PROOF(A) ^ PROOF(B) ^ (A^B->C))
THE PROOF PREDICATE GODEL PROVED DOESN'T EXIST!
C is proven IF c is a theorem in the theory
OR C is derived from other theorems (A^B) in the theory!
It's slightly rearranged from the original specification, a dual tail
end recursive directed acyclic graph of binary deductions!
THEN the Godel Proof continues and INVENTS MULTIPLE PARALLEL THEORIES
...just to PROVE G and yet allow the statement to be TRUE ASWELL (i.e.
unproven in theory 2)
-------
CUT TO PREVIOUS POST..
Here is a Busy Beaver function that literally works to output the
"uncomputable" number sequence BB(1) BB(2) BB(3) ...
function BB(n) {
firstTM = get1stTM#ofSize(n)
lastTM = getlastTM#ofSize(n)
asymptote = 0
while(true) {
for (tm=firstTM, tm<=lastTM, tm++) {
retval = Run1Cycle(tm)
if !null(retval) {
if (find('0',retval)=0) { //unary output
if(retval>asymptote) {
asymptote=retval
display(asymptote)
}
}
}
}
}
}
********
Also, OMEGA can be computed the same way a GODEL STATEMENT IS PROVEN
in 'a different theory'.
The formula for a contradiction in a theory can be written
T |- A & T |- !A
A Godel statement true in theory T1 and proven in theory T2 is
T1 |- G & T2 |- PRV(G)
Programs could also be disjoint into 2.
P1 |- f(a) & P2 |- f(b)
Now we can express a meta-syntax of several parallel programs.
!EXIST(a) Pn |- H1(a) & Pn |- H2(a)
no single computer program can run H1() and H2() on the same input.
This is hard to detect as a pre-parsed syntax error since 'a' could be
a complex formula.
ALL(n,x,y) !(Pn |- H1(x) & Pn |- H2(y) )
That is, no program can call both H1 and H2, even if they are testing
different programs halt values where
T|-HALT(x) = P1|-H1() XOR P2|-H2()
i
.e. the HALT function is computed in a different program to where it
is calculated by functions H1() and H2()
***
Hiding the Halt value may not even be required, since the software is
tested by a DIFFERENT PROGRAM is easy to specify into the syntax,
something like:
T|-HALT(x) = P1|-H1() ^ P1|-H2() ^ P1|-H3() .. P1|-Hn()
where H1() H2() ... Hn() are PROGRAM STUBS inserted into the main
loops of the software to test.
***
SUMMARY OF ABOVE:
Use the GODEL - works in 1 theory and programmed in another method!
Herc
> On Sun, 13 May 2012 10:15:08 -0500, Peter Olcott <OCR4Screen> said:
>
> > The Halting Problem proposes that it will always be impossible to
> > create a halting decider.
>
> The Halting Problem "proposes" no such thing. The Halting Problem is
> simply the problem of whether such a decider (in the form of a Turing
> machine, program, recursive function, what have you) exists. And as
> Turing himself proved, the answer is No. End of story (though of course
> the story is well worth learning).
The Halting Problem combined with the Church Turing Thesis does
suggest exactly that!
i.e. CTT = no new computational system can be more advanced than a
single TM
The Halting Problem may be solvable.
The problem is: Both the Godel Proof and Halting Proof are "copouts"!
"We can't program the function!", but we can formulate why we can't
find the solution instead!
The Godel proof begins...
Assume a PROOF() Predicate exists that inputs a theorem (GODEL NUMBER)
and outputs TRUE IFF a sequence of theorems in the theory conclude
with the final line equal to the input theorem under question.
i.e. a proof of the theorem exists by enumerable axiomatic modus
ponens.
The Proof concludes such a PROOF() Predicate doesn't exist!
Wait! Here it is!
PROOF(C) = C v (PROOF(A) ^ PROOF(B) ^ (A^B->C))
THE PROOF PREDICATE GODEL PROVED DOESN'T EXIST!
C is proven IF c is a theorem in the theory
OR C is derived from other theorems (A^B) in the theory!
It's slightly rearranged from the original specification, a dual tail
end recursive directed acyclic graph of binary deductions!
THEN the Godel Proof continues and INVENTS MULTIPLE PARALLEL THEORIES
...just to PROVE G and yet allow the statement to be TRUE ASWELL (i.e.
unproven in theory 2)
-------
CUT TO PREVIOUS POST..
Here is a Busy Beaver function that literally works to output the
"uncomputable" number sequence BB(1) BB(2) BB(3) ...
function BB(n) {
firstTM = get1stTM#ofSize(n)
lastTM = getlastTM#ofSize(n)
asymptote = 0
while(true) {
for (tm=firstTM, tm<=lastTM, tm++) {
retval = Run1Cycle(tm)
if !null(retval) {
if (find('0',retval)=0) { //unary output
if(retval>asymptote) {
asymptote=retval
display(asymptote)
}
}
}
}
}
}
********
Also, OMEGA can be computed the same way a GODEL STATEMENT IS PROVEN
in 'a different theory'.
The formula for a contradiction in a theory can be written
T |- A & T |- !A
A Godel statement true in theory T1 and proven in theory T2 is
T1 |- G & T2 |- PRV(G)
Programs could also be disjoint into 2.
P1 |- f(a) & P2 |- f(b)
Now we can express a meta-syntax of several parallel programs.
!EXIST(a) Pn |- H1(a) & Pn |- H2(a)
no single computer program can run H1() and H2() on the same input.
This is hard to detect as a pre-parsed syntax error since 'a' could be
a complex formula.
ALL(n,x,y) !(Pn |- H1(x) & Pn |- H2(y) )
That is, no program can call both H1 and H2, even if they are testing
different programs halt values where
T|-HALT(x) = P1|-H1() XOR P2|-H2()
i
.e. the HALT function is computed in a different program to where it
is calculated by functions H1() and H2()
***
Hiding the Halt value may not even be required, since the software is
tested by a DIFFERENT PROGRAM is easy to specify into the syntax,
something like:
T|-HALT(x) = P1|-H1() ^ P1|-H2() ^ P1|-H3() .. P1|-Hn()
where H1() H2() ... Hn() are PROGRAM STUBS inserted into the main
loops of the software to test.
***
SUMMARY OF ABOVE:
Use the GODEL - works in 1 theory and programmed in another method!
Herc
Graham Cooper
May 17, 2012, 2:08:03 AM5/17/12
to
On May 14, 1:15 am, Peter Olcott <OCR4Screen> wrote:
> The Halting Problem proposes that it will always be impossible to create
> a halting decider. This is taken to remain true regardless of any
> The Halting Problem proposes that it will always be impossible to create
> possible advances in technology such as advances in computational
> knowledge representation and reasoning.
>
> If we take this to its logical extreme we could conceive of a Turing
> Machine that has the sum total of every detail of all knowledge about
> every subject stored within its finite states. This same TM could also
> have reasoning ability at least equal to the abilities of the best minds
> in every field. This same machine could also have a natural language
> recognizer for every known human language in the world, such that it
> could be asked any possible question and answer this question using any
> natural language such as English.
>
> I would think that a machine such as this could at least store within
> various permutations of its multitude of internal states the answer to
> whether or not another TM halts on its input. It may not store this
> answer in any single state, this answer might be stored as a very large
> number of permutations of many internal states.
>
> Because the tape of a Turing Machine can be written to and erased, and
> it is of unlimited length, the number of permutations of internal states
> (using the broader definition of machine state) that includes the state
> of the tape, becomes infinite. Maybe a machine such as this can not be
> fooled.
I do something very similar with the different permuations of the same
set of computable functions of the infinite sequence of Universal
Turing Machines that 1 single UTM can emulate or list!
This is my model of computable reals that uses the pseudo-proof that
CARD(R) = CARD(N)
*****
> > Ok we have card(P) > card (N)
> > Now just show card(P) = card(R) (hint look for a surjection and and injection)
> >
>
> Each Turing Machine, TM1, TM2, TM3... outputs an IBS
>
> An infinite subset of Turing Machines are Universal which can output
> all TMs and their IBSs using all possible permutations P of R.
>
> Since the 'uncountable' card(P) > card(N) relies on the free variable *function* P
>
> AD[d] = FLIP( LIST( P(d), d))
>
> all permutations (Reals) are indexed.
>
Pictographically...
ORD = Ordinary Turing Machine
UNI = Universal Turing Machine // can emulate any Turing Machine
TM1 TM2 TM3 TM4 TM5 TM6 TM7 ...
ORD ORD UNI ORD ORD UNI ORD ...
--- --- P1()--- --- P2()--- ...
All permutations P of the general anti-diagonal are computable.
AD[d] = FLIP( LIST( P(d), d))
using the fact different Universal Turing Machines produce different
orders of the infinite set of computable functions.
Herc
Peter Olcott
May 13, 2012, 11:15:08 AM5/13/12
to
Chris Menzel
May 13, 2012, 4:30:49 PM5/13/12
to
On Sun, 13 May 2012 10:15:08 -0500, Peter Olcott <OCR4Screen> said:
> The Halting Problem proposes that it will always be impossible to
> create a halting decider.
> create a halting decider.
Joshua Cranmer
May 14, 2012, 11:52:44 AM5/14/12
to
On 5/13/2012 10:15 AM, Peter Olcott wrote:
> The Halting Problem proposes that it will always be impossible to create
> a halting decider. This is taken to remain true regardless of any
> possible advances in technology such as advances in computational
> knowledge representation and reasoning.
No, you are ascribing to much to a single Theorem. All the proof shows
> The Halting Problem proposes that it will always be impossible to create
> a halting decider. This is taken to remain true regardless of any
> possible advances in technology such as advances in computational
> knowledge representation and reasoning.
is that a Turing machine cannot correctly decide whether or not a Turing
machine will halt. Note that the Church-Turing Thesis suggests that the
most powerful model that is physically realizable is a Turing machine,
but we have been known to overturn these sorts of results before (e.g.,
relativistic modifications to Newtonian mechanics).
> If we take this to its logical extreme we could conceive of a Turing
> Machine that has the sum total of every detail of all knowledge about
> every subject stored within its finite states.
knowledge [1], then your Turing machine cannot exist, since a finite
number of states cannot store an infinite amount of memory.
However, there is also the little matter of "Godel's Incompleteness
Theorem"--any sufficiently powerful proof system (one that can represent
arithmetic) is known to be either inconsistent or incomplete. This
implies that it is impossible to derive all "knowledge" (statements)
from a finite basis of known facts (axioms).
> Because the tape of a Turing Machine can be written to and erased, and
> it is of unlimited length, the number of permutations of internal states
> (using the broader definition of machine state) that includes the state
> of the tape, becomes infinite. Maybe a machine such as this can not be
> fooled.
Escher, Bach." This book is an easy introduction to Godel's
Incompleteness Theorem, how it is proved, and also happily covers
discussions of knowledge that you are so interested in (as well as other
useful topics like Cantor's diagonalization theorem and the Halting
problem). Then see if you hold the same opinions.
[1] It depends on how you define knowledge. If you treat it as logical
entailment from a series of axioms, then it is clear to see that there
is an infinite number of results that can be derived in even basic
systems [e.g., ZFC].
--
Beware of bugs in the above code; I have only proved it correct, not
tried it. -- Donald E. Knuth
Chris Menzel
May 14, 2012, 4:58:00 PM5/14/12
to
On Mon, 14 May 2012 10:52:44 -0500, Joshua Cranmer
<Pidg...@verizon.invalid> said:
> On 5/13/2012 10:15 AM, Peter Olcott wrote:
>> The Halting Problem proposes that it will always be impossible to create
>> a halting decider. This is taken to remain true regardless of any
>> possible advances in technology such as advances in computational
>> knowledge representation and reasoning.
>
> No, you are ascribing to much to a single Theorem. All the proof shows
> is that a Turing machine cannot correctly decide whether or not a
> Turing machine will halt.
Oh, that's all? :-) "Computable" in modern logic and computer science
<Pidg...@verizon.invalid> said:
> On 5/13/2012 10:15 AM, Peter Olcott wrote:
>> The Halting Problem proposes that it will always be impossible to create
>> a halting decider. This is taken to remain true regardless of any
>> possible advances in technology such as advances in computational
>> knowledge representation and reasoning.
>
> No, you are ascribing to much to a single Theorem. All the proof shows
> is that a Turing machine cannot correctly decide whether or not a
> Turing machine will halt.
*means* "computable by a Turing machine" (or equivalent mechanism).
Hence, the proof shows that there is no absolutely no hope of a
computable solution to the Halting Problem. Seems pretty profound to me,
especially when you start cashing out some of its implications, including
a weaker form of Goedels's incompleteness theorem and the undecidability
of first-order validity.
> Note that the Church-Turing Thesis suggests that the most powerful
> model that is physically realizable is a Turing machine,
> but we have been known to overturn these sorts of results
> before (e.g., relativistic modifications to Newtonian mechanics).
>> Because the tape of a Turing Machine can be written to and erased,
>> and it is of unlimited length, the number of permutations of internal
>> states (using the broader definition of machine state) that includes
>> the state of the tape, becomes infinite. Maybe a machine such as this
>> can not be fooled.
>
> Do this: go to your local library and check out a book entitled "Godel,
> Escher, Bach." This book is an easy introduction to Godel's
> Incompleteness Theorem, how it is proved, and also happily covers
> discussions of knowledge that you are so interested in (as well as other
> useful topics like Cantor's diagonalization theorem and the Halting
> problem). Then see if you hold the same opinions.
I believe he's been given this sort of sound advice any number of times.
>> and it is of unlimited length, the number of permutations of internal
>> states (using the broader definition of machine state) that includes
>> the state of the tape, becomes infinite. Maybe a machine such as this
>> can not be fooled.
>
> Do this: go to your local library and check out a book entitled "Godel,
> Escher, Bach." This book is an easy introduction to Godel's
> Incompleteness Theorem, how it is proved, and also happily covers
> discussions of knowledge that you are so interested in (as well as other
> useful topics like Cantor's diagonalization theorem and the Halting
> problem). Then see if you hold the same opinions.
> [1] It depends on how you define knowledge. If you treat it as logical
> entailment from a series of axioms, then it is clear to see that there
> is an infinite number of results that can be derived in even basic
> systems [e.g., ZFC].
infinitely many axioms. I wouldn't call such a system "basic" in the
sense you seem to have in mind.
Joshua Cranmer
May 14, 2012, 5:57:09 PM5/14/12
to
On 5/14/2012 3:58 PM, Chris Menzel wrote:
> On Mon, 14 May 2012 10:52:44 -0500, Joshua Cranmer
> On Mon, 14 May 2012 10:52:44 -0500, Joshua Cranmer
>> No, you are ascribing to much to a single Theorem. All the proof shows
>> is that a Turing machine cannot correctly decide whether or not a
>> Turing machine will halt.
>
> Oh, that's all? :-)
Note that I said "single" theorem. Combine it with other theorems and
>> is that a Turing machine cannot correctly decide whether or not a
>> Turing machine will halt.
>
> Oh, that's all? :-)
fairly trivial results and you get an independent proof of "mathematics
is incomplete" (note that you can prove the Halting problem from Godel's
theorem and v.v.).
>> Note that the Church-Turing Thesis suggests that the most powerful
>> model that is physically realizable is a Turing machine,
>
> The Church-Turing Thesis has nothing to do with physical realizability.
construct mathematical models of computation that are more powerful
(Turing oracles are a good example), but since these models are
unattainable in more practical settings, they're excluded from the
notion of "effectively computable".
Chris Menzel
May 14, 2012, 7:58:49 PM5/14/12
to
On Mon, 14 May 2012 16:57:09 -0500, Joshua Cranmer
<Pidg...@verizon.invalid> said:
> On 5/14/2012 3:58 PM, Chris Menzel wrote:
>> On Mon, 14 May 2012 10:52:44 -0500, Joshua Cranmer
>>> No, you are ascribing to much to a single Theorem. All the proof
>>> shows is that a Turing machine cannot correctly decide whether or
>>> not a Turing machine will halt.
>>
>> Oh, that's all? :-)
>
> Note that I said "single" theorem. Combine it with other theorems and
> fairly trivial results and you get an independent proof of
> "mathematics is incomplete" (note that you can prove the Halting
> problem from Godel's theorem and v.v.).
So I've heard. I'm still not getting the point of "All the proof
<Pidg...@verizon.invalid> said:
> On 5/14/2012 3:58 PM, Chris Menzel wrote:
>> On Mon, 14 May 2012 10:52:44 -0500, Joshua Cranmer
>>> No, you are ascribing to much to a single Theorem. All the proof
>>> shows is that a Turing machine cannot correctly decide whether or
>>> not a Turing machine will halt.
>>
>> Oh, that's all? :-)
>
> Note that I said "single" theorem. Combine it with other theorems and
> fairly trivial results and you get an independent proof of
> "mathematics is incomplete" (note that you can prove the Halting
> problem from Godel's theorem and v.v.).
shows...". The proof shows something very profound. "All the proof
shows..." is the sort of thing you say about a proof that is not a big
deal, a proof that appears to show more than it actually does. But
whatever. It's not a point worth debating.
>>> Note that the Church-Turing Thesis suggests that the most powerful
>>> model that is physically realizable is a Turing machine,
>>
>> The Church-Turing Thesis has nothing to do with physical realizability.
>
> It's one of the interpretations of statements. The point is that we can
> construct mathematical models of computation that are more powerful
> (Turing oracles are a good example), but since these models are
> unattainable in more practical settings,
practical settings". Computability by a TM has nothing whatever to do
with practicality. A given TM might require more storage space than is
realizable in the physical universe and, even if realizable, it might
take trillions of years to do its calculation.
> they're excluded from the notion of "effectively computable".
because they are not equivalent to what "computable" *means*, i.e.,
computable by a Turing Machine.
Joshua Cranmer
May 14, 2012, 9:19:40 PM5/14/12
to
On 5/14/2012 6:58 PM, Chris Menzel wrote:
> On Mon, 14 May 2012 16:57:09 -0500, Joshua Cranmer
> On Mon, 14 May 2012 16:57:09 -0500, Joshua Cranmer
>> they're excluded from the notion of "effectively computable".
>
> That is not why they are excluded. They are excluded by definition,
> because they are not equivalent to what "computable" *means*, i.e.,
> computable by a Turing Machine.
I'm using the definition of the Church-Turing thesis as follows:
>
> That is not why they are excluded. They are excluded by definition,
> because they are not equivalent to what "computable" *means*, i.e.,
> computable by a Turing Machine.
"Every 'effectively computable' function is also Turing-computable."
"Computable" (as an unmodified adjective) is often taken to mean
Turing-computable, but "effectively computable" is effectively an atomic
phrase with the notion that amounts to "a model of computation that is
more or less realizable as an algorithm". It's clear that things like
Turing oracles are excluded as far as the Church-Turing thesis is
concerned, but not because they aren't Turing machines (that makes it
circular).
Peter Olcott
May 15, 2012, 5:51:21 PM5/15/12
to
On 5/14/2012 10:52 AM, Joshua Cranmer wrote:
> On 5/13/2012 10:15 AM, Peter Olcott wrote:
>> The Halting Problem proposes that it will always be impossible to create
>> a halting decider. This is taken to remain true regardless of any
>> possible advances in technology such as advances in computational
>> knowledge representation and reasoning.
>
> No, you are ascribing to much to a single Theorem. All the proof shows
> is that a Turing machine cannot correctly decide whether or not a
> Turing machine will halt. Note that the Church-Turing Thesis suggests
> that the most powerful model that is physically realizable is a Turing
> machine, but we have been known to overturn these sorts of results
> before (e.g., relativistic modifications to Newtonian mechanics).
>
>> If we take this to its logical extreme we could conceive of a Turing
>> Machine that has the sum total of every detail of all knowledge about
>> every subject stored within its finite states.
>
> If we accept the hypothesis that there is an infinite amount of
> knowledge [1], then your Turing machine cannot exist, since a finite
> number of states cannot store an infinite amount of memory.
>
It can store it on the infinite tape.
> On 5/13/2012 10:15 AM, Peter Olcott wrote:
>> The Halting Problem proposes that it will always be impossible to create
>> a halting decider. This is taken to remain true regardless of any
>> possible advances in technology such as advances in computational
>> knowledge representation and reasoning.
>
> No, you are ascribing to much to a single Theorem. All the proof shows
> is that a Turing machine cannot correctly decide whether or not a
> Turing machine will halt. Note that the Church-Turing Thesis suggests
> that the most powerful model that is physically realizable is a Turing
> machine, but we have been known to overturn these sorts of results
> before (e.g., relativistic modifications to Newtonian mechanics).
>
>> If we take this to its logical extreme we could conceive of a Turing
>> Machine that has the sum total of every detail of all knowledge about
>> every subject stored within its finite states.
>
> If we accept the hypothesis that there is an infinite amount of
> knowledge [1], then your Turing machine cannot exist, since a finite
> number of states cannot store an infinite amount of memory.
>
> However, there is also the little matter of "Godel's Incompleteness
> Theorem"--any sufficiently powerful proof system (one that can
> represent arithmetic) is known to be either inconsistent or
> incomplete. This implies that it is impossible to derive all
> "knowledge" (statements) from a finite basis of known facts (axioms).
>
do not have sufficient understanding of the mathematics of the semantics
of natural language.
His theorem is based on the same sort of ill-formed question that
derives the basis for the Halting Problem.
Joshua Cranmer
May 15, 2012, 6:37:40 PM5/15/12
to
On 5/15/2012 4:51 PM, Peter Olcott wrote:
> On 5/14/2012 10:52 AM, Joshua Cranmer wrote:
>> On 5/13/2012 10:15 AM, Peter Olcott wrote:
>>> The Halting Problem proposes that it will always be impossible to create
>>> a halting decider. This is taken to remain true regardless of any
>>> possible advances in technology such as advances in computational
>>> knowledge representation and reasoning.
>>
>> No, you are ascribing to much to a single Theorem. All the proof shows
>> is that a Turing machine cannot correctly decide whether or not a
>> Turing machine will halt. Note that the Church-Turing Thesis suggests
>> that the most powerful model that is physically realizable is a Turing
>> machine, but we have been known to overturn these sorts of results
>> before (e.g., relativistic modifications to Newtonian mechanics).
>>
>>> If we take this to its logical extreme we could conceive of a Turing
>>> Machine that has the sum total of every detail of all knowledge about
>>> every subject stored within its finite states.
>>
>> If we accept the hypothesis that there is an infinite amount of
>> knowledge [1], then your Turing machine cannot exist, since a finite
>> number of states cannot store an infinite amount of memory.
>>
> It can store it on the infinite tape.
You said "stored within its finite states", not on the infinite tape.
> On 5/14/2012 10:52 AM, Joshua Cranmer wrote:
>> On 5/13/2012 10:15 AM, Peter Olcott wrote:
>>> The Halting Problem proposes that it will always be impossible to create
>>> a halting decider. This is taken to remain true regardless of any
>>> possible advances in technology such as advances in computational
>>> knowledge representation and reasoning.
>>
>> No, you are ascribing to much to a single Theorem. All the proof shows
>> is that a Turing machine cannot correctly decide whether or not a
>> Turing machine will halt. Note that the Church-Turing Thesis suggests
>> that the most powerful model that is physically realizable is a Turing
>> machine, but we have been known to overturn these sorts of results
>> before (e.g., relativistic modifications to Newtonian mechanics).
>>
>>> If we take this to its logical extreme we could conceive of a Turing
>>> Machine that has the sum total of every detail of all knowledge about
>>> every subject stored within its finite states.
>>
>> If we accept the hypothesis that there is an infinite amount of
>> knowledge [1], then your Turing machine cannot exist, since a finite
>> number of states cannot store an infinite amount of memory.
>>
> It can store it on the infinite tape.
>> However, there is also the little matter of "Godel's Incompleteness
>> Theorem"--any sufficiently powerful proof system (one that can
>> represent arithmetic) is known to be either inconsistent or
>> incomplete. This implies that it is impossible to derive all
>> "knowledge" (statements) from a finite basis of known facts (axioms).
>>
> He was wrong as I have already shown, yet no one understood because they
> do not have sufficient understanding of the mathematics of the semantics
> of natural language.
Bachelor's in CS seriously knows more about "the mathematics of the
semantics of natural language" than the people who formalized
mathematics in the first place?
It's been pointed out before that every time you try to state things in
a more formal setting, your results are either wrong or uninteresting.
And yet you still do not see this as a sign that maybe it is you who is
wrong and not everybody else.
Again, I reiterate my earlier imperative:
GO READ "Godel, Escher, Bach." Until you do that, stop arguing that
Godel's incompleteness theorem and the Halting problem are wrong--you're
just making it more and more clear that you have no idea what you are
talking about.
Peter Olcott
May 15, 2012, 6:49:01 PM5/15/12
to
string contains semantic meaning.
> It's been pointed out before that every time you try to state things
> in a more formal setting, your results are either wrong or
> uninteresting. And yet you still do not see this as a sign that maybe
> it is you who is wrong and not everybody else.
details, but I am not
wrong that the Halting Problem is entirely based on an ill-formed question.
>
> Again, I reiterate my earlier imperative:
> GO READ "Godel, Escher, Bach." Until you do that, stop arguing that
> Godel's incompleteness theorem and the Halting problem are
> wrong--you're just making it more and more clear that you have no idea
> what you are talking about.
>
seems to escape everyone of you.
LudovicoVan
May 15, 2012, 6:52:09 PM5/15/12
to
"Joshua Cranmer" <Pidg...@verizon.invalid> wrote in message
news:jouls3$63u$1...@dont-email.me...
> You seriously believe that an amateur mathematician with at best a
> Bachelor's in CS seriously knows more about "the mathematics of the
> semantics of natural language" than the people who formalized mathematics
> in the first place?
That argument is based on a fallacy. I think you'd be better off and
definitely correct in just saying that he doesn't know what he is talking
about.
-LV
news:jouls3$63u$1...@dont-email.me...
> You seriously believe that an amateur mathematician with at best a
> Bachelor's in CS seriously knows more about "the mathematics of the
> semantics of natural language" than the people who formalized mathematics
> in the first place?
definitely correct in just saying that he doesn't know what he is talking
about.
-LV
LudovicoVan
May 15, 2012, 6:53:40 PM5/15/12
to
"LudovicoVan" <ju...@diegidio.name> wrote in message
news:joummr$ja8$1...@speranza.aioe.org...
I have for now classified P.O. as a troll.
-LV
news:joummr$ja8$1...@speranza.aioe.org...
-LV
Peter Olcott
May 15, 2012, 7:08:19 PM5/15/12
to
It is generally a mind-closing thing to classify people.
LudovicoVan
May 15, 2012, 7:21:32 PM5/15/12
to
"Peter Olcott" <OCR4Screen> wrote in message
news:_L2dnTehVbp-fC_S...@giganews.com...
-LV
news:_L2dnTehVbp-fC_S...@giganews.com...
> On 5/15/2012 5:53 PM, LudovicoVan wrote:
>> I have for now classified P.O. as a troll.
>
>> I have for now classified P.O. as a troll.
>
> I still have not classified you yet.
> It is generally a mind-closing thing to classify people.
No worries, my classifications are dynamic...
> It is generally a mind-closing thing to classify people.
-LV
H.J. Sander Bruggink
May 16, 2012, 4:46:43 AM5/16/12
to
On 05/16/2012 12:49 AM, Peter Olcott wrote:
> On 5/15/2012 5:37 PM, Joshua Cranmer wrote:
>> On 5/15/2012 4:51 PM, Peter Olcott wrote:
>>> On 5/14/2012 10:52 AM, Joshua Cranmer wrote:
>>>> If we accept the hypothesis that there is an infinite amount of
>>>> knowledge [1], then your Turing machine cannot exist, since a finite
>>>> number of states cannot store an infinite amount of memory.
>>>>
>>> It can store it on the infinite tape.
At any time during the Turing Machine's computation, this "infinite"
> On 5/15/2012 5:37 PM, Joshua Cranmer wrote:
>> On 5/15/2012 4:51 PM, Peter Olcott wrote:
>>> On 5/14/2012 10:52 AM, Joshua Cranmer wrote:
>>>> If we accept the hypothesis that there is an infinite amount of
>>>> knowledge [1], then your Turing machine cannot exist, since a finite
>>>> number of states cannot store an infinite amount of memory.
>>>>
>>> It can store it on the infinite tape.
tape only contains a finite amount of information.
>> You seriously believe that an amateur mathematician with at best a
>> Bachelor's in CS seriously knows more about "the mathematics of the
>> semantics of natural language" than the people who formalized
>> mathematics in the first place?
>>
>
> Absolutely positively when these same people insist that the empty
> string contains semantic meaning.
they claim that NO STRING has semantic meaning of itself. You need some
kind of mapping from strings to meanings to understand the strings, and
this mapping may indeed attach a meaning to the empty string.
Just to show you what I mean, please answer the following questions:
* Wem denen amlacht diem pro elvenbas?
* Wie vond de zwaartekracht uit?
* Was ist die Bedeutung der leeren Zeichenkette?
>
> You are still incorrect on this point. What is completely obvious to me
> seems to escape everyone of you.
might condider the possibility that you actually are wrong.
Sander
Chris Menzel
May 16, 2012, 4:44:40 PM5/16/12
to
On Mon, 14 May 2012 20:19:40 -0500, Joshua Cranmer
<Pidg...@verizon.invalid> said:
> On 5/14/2012 6:58 PM, Chris Menzel wrote:
>> On Mon, 14 May 2012 16:57:09 -0500, Joshua Cranmer
>>> they're excluded from the notion of "effectively computable".
>>
>> That is not why they are excluded. They are excluded by definition,
>> because they are not equivalent to what "computable" *means*, i.e.,
>> computable by a Turing Machine.
>
> I'm using the definition of the Church-Turing thesis as follows:
> "Every 'effectively computable' function is also Turing-computable."
OK, it wasn't clear to me that you were using "effectively computable"
<Pidg...@verizon.invalid> said:
> On 5/14/2012 6:58 PM, Chris Menzel wrote:
>> On Mon, 14 May 2012 16:57:09 -0500, Joshua Cranmer
>>> they're excluded from the notion of "effectively computable".
>>
>> That is not why they are excluded. They are excluded by definition,
>> because they are not equivalent to what "computable" *means*, i.e.,
>> computable by a Turing Machine.
>
> I'm using the definition of the Church-Turing thesis as follows:
> "Every 'effectively computable' function is also Turing-computable."
in the informal sense meant in the C-T thesis.
> "Computable" (as an unmodified adjective) is often taken to mean
> Turing-computable, but "effectively computable" is effectively an
> atomic phrase with the notion that amounts to "a model of computation
> that is more or less realizable as an algorithm". It's clear that
> things like Turing oracles are excluded as far as the Church-Turing
> thesis is concerned, but not because they aren't Turing machines (that
> makes it circular).
*stipulation* of the meaning of "effectively computable". (That is the
only way I can understand your talk of it "excluding" other models of
computation.) If so, that is a misunderstanding. The C-T Thesis is a
*conjecture*, not a stipulation: Any function for which there is an
intuitive algorithm can in fact be computed by a Turing Machine.
Otherwise put, it is the claim that the *formal* notion of a Turing
Machine complete captures our *informal* idea of mechanical
calculability. It is therefore falsifiable: Should we come up with an
intuitive algorithm for calculating a function that is known not to be
Turing computable, then the conjecture will have been proved false. So
far, the conjecture seems to be in good shape.
Chris Menzel
May 16, 2012, 5:04:34 PM5/16/12
to
On Tue, 15 May 2012 17:49:01 -0500, Peter Olcott <OCR4Screen> said:
> ...
theoretical computer science. His brilliant cryptographic work in WWII
was a major factor in the defeat of Germany. He is uniformly
acknowledged as one of the greatest minds of the 20th century. But he
was confused about the Halting Problem (and you, by contrast, are not).
You really must think this one through.
> ...
> I may have been wrong about some of the Theory of Computation specific
> details, but I am not wrong that the Halting Problem is entirely based
> on an ill-formed question.
Let me see if I understanding. Turing's work forms the foundation of
> details, but I am not wrong that the Halting Problem is entirely based
> on an ill-formed question.
theoretical computer science. His brilliant cryptographic work in WWII
was a major factor in the defeat of Germany. He is uniformly
acknowledged as one of the greatest minds of the 20th century. But he
was confused about the Halting Problem (and you, by contrast, are not).
You really must think this one through.
LudovicoVan
May 16, 2012, 5:29:17 PM5/16/12
to
"Chris Menzel" <cme...@remove-this.tamu.edu> wrote in message
news:slrnjr85j2....@philebus.tamu.edu...
Yet that is a basic fallacy: for coherence, no one should be doing research
anymore.
-LV
news:slrnjr85j2....@philebus.tamu.edu...
anymore.
-LV
Peter Olcott
May 16, 2012, 6:23:55 PM5/16/12
to
On 5/16/2012 3:46 AM, H.J. Sander Bruggink wrote:
> On 05/16/2012 12:49 AM, Peter Olcott wrote:
>> On 5/15/2012 5:37 PM, Joshua Cranmer wrote:
>>> On 5/15/2012 4:51 PM, Peter Olcott wrote:
>>>> On 5/14/2012 10:52 AM, Joshua Cranmer wrote:
>>>>> If we accept the hypothesis that there is an infinite amount of
>>>>> knowledge [1], then your Turing machine cannot exist, since a finite
>>>>> number of states cannot store an infinite amount of memory.
>>>>>
>>>> It can store it on the infinite tape.
>
> At any time during the Turing Machine's computation, this "infinite"
> tape only contains a finite amount of information.
>
>>> You seriously believe that an amateur mathematician with at best a
>>> Bachelor's in CS seriously knows more about "the mathematics of the
>>> semantics of natural language" than the people who formalized
>>> mathematics in the first place?
>>>
>>
>> Absolutely positively when these same people insist that the empty
>> string contains semantic meaning.
>
> They don't claim that the empty string has semantic meaning of itself,
> they claim that NO STRING has semantic meaning of itself. You need
> some kind of mapping from strings to meanings to understand the
> strings, and this mapping may indeed attach a meaning to the empty
> string.
A UTM can not directly execute an empty string because the contents of
> On 05/16/2012 12:49 AM, Peter Olcott wrote:
>> On 5/15/2012 5:37 PM, Joshua Cranmer wrote:
>>> On 5/15/2012 4:51 PM, Peter Olcott wrote:
>>>> On 5/14/2012 10:52 AM, Joshua Cranmer wrote:
>>>>> If we accept the hypothesis that there is an infinite amount of
>>>>> knowledge [1], then your Turing machine cannot exist, since a finite
>>>>> number of states cannot store an infinite amount of memory.
>>>>>
>>>> It can store it on the infinite tape.
>
> At any time during the Turing Machine's computation, this "infinite"
> tape only contains a finite amount of information.
>
>>> You seriously believe that an amateur mathematician with at best a
>>> Bachelor's in CS seriously knows more about "the mathematics of the
>>> semantics of natural language" than the people who formalized
>>> mathematics in the first place?
>>>
>>
>> Absolutely positively when these same people insist that the empty
>> string contains semantic meaning.
>
> They don't claim that the empty string has semantic meaning of itself,
> they claim that NO STRING has semantic meaning of itself. You need
> some kind of mapping from strings to meanings to understand the
> strings, and this mapping may indeed attach a meaning to the empty
> string.
the empty string provide insufficient details.
>
> Just to show you what I mean, please answer the following questions:
> * Wem denen amlacht diem pro elvenbas?
> * Wie vond de zwaartekracht uit?
> * Was ist die Bedeutung der leeren Zeichenkette?
>
>>
>> You are still incorrect on this point. What is completely obvious to me
>> seems to escape everyone of you.
>
> Since it is completely obvious to everyone else that you are wrong,
> you might condider the possibility that you actually are wrong.
>
> Sander
>
Peter Olcott
May 16, 2012, 6:27:44 PM5/16/12
to
developed to make my point unambiguously understood to be clearly
correct, even now, and much less so then.
Pete Olcott
Jun 15, 2017, 9:42:27 PM6/15/17
to
Pete Olcott
Jun 16, 2017, 1:11:03 AM6/16/17
to
On 6/15/2017 10:07 PM, graham...@gmail.com wrote:
> Ahh the good ole days!
>
> OK since PETER O. FAMOUSLY INVENTED the HALTING-DISPROOF I'll outline it here!
>
>
> a TM exists that outputs a SEQUENCE of TURING NUMBERS (number of programs that can be run...)
>
>
>
> TM-MASTER (X) = y
> -IFF-
> TM_y is the Xth Counted Turing Machine with property
>
>
> TM_y( p ) = 1 -IFF- TM_p halts with probability p>0.5+epsilon
>
>
> SIMILARLY
>
> TM_z( p ) = 1 -IFF- TM_p infinite loops with probability p>0.5+epsilon
>
>
> THEREFORE BY CONVERGANT HALT CALCULATIONS THE HALTING PROOF IS DIS-PROVEN
> Q.E.D.
>
As it actually turns out to be, the Halting Problem proof itself is infinitely recursive thus never completes its evaluation. I delve into this further on the Comp.Theory forum.
--
(Γ ⊨ _FS A) ≡ (Γ ⊢ _FS A)
>
> OK since PETER O. FAMOUSLY INVENTED the HALTING-DISPROOF I'll outline it here!
>
>
> a TM exists that outputs a SEQUENCE of TURING NUMBERS (number of programs that can be run...)
>
>
>
> TM-MASTER (X) = y
> -IFF-
> TM_y is the Xth Counted Turing Machine with property
>
>
> TM_y( p ) = 1 -IFF- TM_p halts with probability p>0.5+epsilon
>
>
> SIMILARLY
>
> TM_z( p ) = 1 -IFF- TM_p infinite loops with probability p>0.5+epsilon
>
>
> THEREFORE BY CONVERGANT HALT CALCULATIONS THE HALTING PROOF IS DIS-PROVEN
> Q.E.D.
>
As it actually turns out to be, the Halting Problem proof itself is infinitely recursive thus never completes its evaluation. I delve into this further on the Comp.Theory forum.
--
(Γ ⊨ _FS A) ≡ (Γ ⊢ _FS A)
0 new messages