"RichD" <r_delaney2001@yahoo.com> wrote in message
news:07e2f776-7bcf-4783-bd0e-f014e4434dc0@googlegroups.com...
> Presumably, most here are familiar with the concept of undecidability.
>
> My question is simple, though perhaps not the answer: Godel published
> his results first, hence does Turing's non-computability theorem
> (the halting problem), follow as a corollary? What is the relationship
> between these seemingly parallel theorems?
One thing that has always concerned me about the Halting idea is that
we as humans can decide that something is undecidable but our brains do not
have to halt!
Reply by bitrex●January 29, 20162016-01-29
Les Cargill <lcargill99@comcast.com> Wrote in message:
> RichD wrote:
>> Presumably, most here are familiar with the concept of undecidability.
>>
>> My question is simple, though perhaps not the answer: Godel published
>> his results first, hence does Turing's non-computability theorem
>> (the halting problem), follow as a corollary? What is the relationship
>> between these seemingly parallel theorems?
>>
>
> I'm pretty sure Turing used Godel as part of his design of The Halting
> Problem. It could effectively be considered a restatement of it.
>
> There's little parallel about them; they're statements of the same basic
> problem. At some level, they're quite different, at
> another they are exactly the same.
>
> But still, I'd like to see a more direct path from A to B, because if you
> look at their papers, they're talking different languages.
If the only form of repetition which a program uses is a classical "for"
loop (where then number of iterations is fixed in advance), then clearly
the program will terminate eventually.
The hard case (in terms of any practical attempt at deciding termination)
is the use of "while (<predicate>) { do_stuff(); }". Determining whether
the loop will terminate boils down to determining whether the predicate
will eventually become false. So the general case of deciding termination
(Turing's problem) boils down to a decision procedure for predicate logic
(Goedel's problem).
Reply by RichD●January 24, 20162016-01-24
On January 23, Piergiorgio Sartor wrote:
> > My question is simple, though perhaps not the answer: Godel published
> > his results first, hence does Turing's non-computability theorem
> > (the halting problem), follow as a corollary? What is the relationship
> > between these seemingly parallel theorems?
>
> You might think the Turing statement as an
> application, for the Turing Machines, of
> the Godel's results.
yes, something like:
Godel: "Undecidable propositions exist."
Turing: "And here's one..."
But still, I'd like to see a more direct path from A to B, because
if you look at their papers, they're talking different languages.
--
Rich
Reply by Piergiorgio Sartor●January 23, 20162016-01-23
On 2016-01-23 05:02, RichD wrote:
> Presumably, most here are familiar with the concept of undecidability.
>
> My question is simple, though perhaps not the answer: Godel published
> his results first, hence does Turing's non-computability theorem
> (the halting problem), follow as a corollary? What is the relationship
> between these seemingly parallel theorems?
You might think the Turing statement as an
application, for the Turing Machines, of
the Godel's results.
bye,
--
piergiorgio
Reply by Les Cargill●January 23, 20162016-01-23
RichD wrote:
> Presumably, most here are familiar with the concept of undecidability.
>
> My question is simple, though perhaps not the answer: Godel published
> his results first, hence does Turing's non-computability theorem
> (the halting problem), follow as a corollary? What is the relationship
> between these seemingly parallel theorems?
>
I'm pretty sure Turing used Godel as part of his design of The Halting
Problem. It could effectively be considered a restatement of it.
There's little parallel about them; they're statements of the same basic
problem. At some level, they're quite different, at
another they are exactly the same.
The Turing version depends on the reliable productivity of
a tape factory, somewhere.
Of course, historically, the great cosmic joke is that Godel
( who was nominally German ) was an unwitting accomplice to
the efforts of Bletchley Park in breaking Enigma.
I am very sure you cannot make stuff like that up. But phrased
properly. the joke is:
My dog has no nose.
How does he smell?
Awful.
> --
> Rich
>
--
Les Cargill
Reply by RichD●January 23, 20162016-01-23
Presumably, most here are familiar with the concept of undecidability.
My question is simple, though perhaps not the answer: Godel published
his results first, hence does Turing's non-computability theorem
(the halting problem), follow as a corollary? What is the relationship
between these seemingly parallel theorems?
--
Rich