Prev: Can Rosser 1936 be Extended? Alan Turing vs. Martin Davis et. al.
Next: Did Turing 1937 Really Prove the Entscheidungsproblem Unsolvable?
From: Charlie-Boo on 4 Jun 2010 00:06
On May 31, 6:35 pm, Rupert <rupertmccal...(a)yahoo.com> wrote:
> On Jun 1, 2:27 am, Charlie-Boo <shymath...(a)gmail.com> wrote:
>
>
>
>
>
> > Wikipedia:
>
> > “In 1936 and 1937 Alonzo Church and Alan Turing respectively,
> > published independent papers showing that it is impossible to decide
> > algorithmically whether statements in arithmetic are true or false,
> > and thus a general solution to the Entscheidungsproblem is impossible.
>
> > Alonzo Church, ‘A note on the Entscheidungsproblem’, Journal of
> > Symbolic Logic, 1 (1936), pp 40–41
>
> > Alan Turing, ‘On computable numbers, with an application to the
> > Entscheidungsproblem’, Proceedings of the London Mathematical Society,
> > Series 2, 42 (1937), pp 230–265”
>
> > However, if the Entscheidungsproblem were solvable, then we could
> > determine (and thus prove) whether the system is consistent by asking
> > whether the sentence 0=1 is provable, as provability is expressible.
>
> If the Entschiedungsproblem were solvable then you could determine
> whether PA is consistent. But it doesn't necessarily follow that you
> would be able to prove that PA is consistent in PA. Solving the
> Entscheidungsproblem just means you have an algorithm for answering
> the question, it doesn't say anything about supplying a proof in some
> theory T of the answer.

Not so. If a set is recursive then there is a wff that represents it
and whose negation represents its complement. That might be called
"defines" by some.

C-B

>
>
> > So don’t we have a proof that is (1) way simpler, and (2) way earlier,
> > than Church and Turing?
>
> > C-B- Hide quoted text -
>
> - Show quoted text -- Hide quoted text -
>
> - Show quoted text -

From: Charlie-Boo on 4 Jun 2010 00:08
On Jun 1, 3:18 pm, George Greene <gree...(a)email.unc.edu> wrote:
> On May 31, 12:27 pm, Charlie-Boo <shymath...(a)gmail.com> wrote:
>
> > Alonzo Church, ‘A note on the Entscheidungsproblem’, Journal of
> > Symbolic Logic, 1 (1936), pp 40–41
>
> > Alan Turing, ‘On computable numbers, with an application to the
> > Entscheidungsproblem’, Proceedings of the London Mathematical Society,
> > Series 2, 42 (1937), pp 230–265”
>
> > However, if the Entscheidungsproblem were solvable, then we could
> > determine (and thus prove) whether the system is consistent by asking
> > whether the sentence 0=1 is provable, as provability is expressible.
>
> > So don’t we have a proof that is (1) way simpler, and (2) way earlier,
> > than Church and Turing?
>
> Why do you say "So" ??

It's way simpler because it's 1% as long. Godel's 2nd Incompleteness
Theorem was proven in 1931.

C-B

> "So" implies that something is following from some prior result.
> Where is your prior result?  Who simply showed that the Eproblem
> was unsovlable PRIOR to this??

From: Charlie-Boo on 4 Jun 2010 00:10
On Jun 1, 3:19 pm, George Greene <gree...(a)email.unc.edu> wrote:
> On May 31, 6:35 pm, Rupert <rupertmccal...(a)yahoo.com> wrote:
>
> > If the Entschiedungsproblem were solvable then you could determine
> > whether PA is consistent. But it doesn't necessarily follow that you
> > would be able to prove that PA is consistent in PA. Solving the
> > Entscheidungsproblem just means you have an algorithm for answering
> > the question, it doesn't say anything about supplying a proof in some
> > theory T of the answer.
>
> The question said, "since provability is expressible".
> Is provability in PA "expressible" in PA ??

What is the premise for Godel's 1st Incompleteness Theorem? (No, not
the hokey ill-defined (vague and informal) "a sufficient amount of
arithmetic can be formalized" silliness.)

C-B

From: Charlie-Boo on 4 Jun 2010 00:13
On Jun 1, 4:07 pm, Aatu Koskensilta <aatu.koskensi...(a)uta.fi> wrote:
> Charlie-Boo <shymath...(a)gmail.com> writes:
> > So don’t we have a proof that is (1) way simpler, and (2) way earlier,
> > than Church and Turing?
>
> No. What proof are you thinking of?
>
> --
> Aatu Koskensilta (aatu.koskensi...(a)uta.fi)
>
> "Wovon man nicht sprechan kann, darüber muss man schweigen"
>  - Ludwig Wittgenstein, Tractatus Logico-Philosophicus

What do you call someone who asks questions for which they know the
response? Something like "fuckwit", I believe.

C-B

Posting limit reached. :(
First  |  Prev  | 
Pages: 1 2
Prev: Can Rosser 1936 be Extended? Alan Turing vs. Martin Davis et. al.
Next: Did Turing 1937 Really Prove the Entscheidungsproblem Unsolvable?