Search All of the Math Forum:

Views expressed in these public forums are not endorsed by Drexel University or The Math Forum.

Topic: An uncomputable finite number.
Replies: 61   Last Post: Apr 15, 2012 2:01 AM

 Messages: [ Previous | Next ]
 Frederick Williams Posts: 2,166 Registered: 10/4/10
Re: An uncomputable finite number.
Posted: Mar 28, 2012 1:15 PM

"David C. Ullrich" wrote:

>
> A simpler more striking example: Assume for the sake of argument
> that GC is undecidable (in whatever system you like).
> Let n = 1 if GC is true and 0 if GC is false. Then we will
> never know the value of n. But n is nonetheless computable:
> One of the following two algorithms computes it:
>
> def f(): return 1
>
> def g(): return 0
>
> So there _is_ an algorithm that computes n.

The OP might be interested in an altogether different conclusion (in
brief: that the converse of the Church-Turing thesis is false) to be
found in:

'Constructive truth in practice' by Douglas S Bridges
collected in: 'Truth in mathematics' edited by H G Dales
and G Oliveri, OUP, 1998.

Naturally, I have no opinion on the matter myself. I'm just offering
the reference in furtherance of the free exchange of ideas, and love and
peace among men.

So, if one was to formalise the theory of recursive functions in Heyting
Arithmetic, would any fewer functions be provably recursive?

--
When a true genius appears in the world, you may know him by
this sign, that the dunces are all in confederacy against him.
Jonathan Swift: Thoughts on Various Subjects, Moral and Diverting

Date Subject Author
3/28/12 namducnguyen
3/28/12 ross.finlayson@gmail.com
3/28/12 trj
3/28/12 jbriggs444@gmail.com
3/28/12 David C. Ullrich
3/28/12 MoeBlee
3/28/12 Frederick Williams
3/28/12 Frederick Williams
3/28/12 ross.finlayson@gmail.com
3/28/12 Herman Rubin
3/28/12 MoeBlee
3/28/12 jbriggs444@gmail.com
3/28/12 namducnguyen
3/29/12 quasi
3/29/12 namducnguyen
3/29/12 ross.finlayson@gmail.com
3/29/12 quasi
3/29/12 namducnguyen
3/29/12 quasi
3/29/12 namducnguyen
3/29/12 quasi
3/29/12 namducnguyen
3/29/12 quasi
3/29/12 quasi
3/29/12 Frederick Williams
3/29/12 MoeBlee
3/29/12 ross.finlayson@gmail.com
3/29/12 MoeBlee
3/29/12 ross.finlayson@gmail.com
3/29/12 MoeBlee
3/29/12 ross.finlayson@gmail.com
3/29/12 MoeBlee
3/29/12 ross.finlayson@gmail.com
3/29/12 MoeBlee
3/29/12 MoeBlee
3/29/12 MoeBlee
3/29/12 MoeBlee
3/29/12 David C. Ullrich
3/28/12 Tim Little
3/29/12 David C. Ullrich
3/30/12 Tim Little
3/29/12 namducnguyen
3/29/12 namducnguyen
3/30/12 namducnguyen
3/30/12 quasi
3/30/12 MoeBlee
4/2/12 quasi
4/3/12 Frederick Williams
4/3/12 quasi
3/30/12 namducnguyen
3/31/12 quasi
3/31/12 ross.finlayson@gmail.com