[FOM] Counterfactuals in relative computability theory

[martdowd at aol.com]

 Colin McLarty writes:


Church's Thesis would be shown false if someone exhibited a provably non-recursive function together with a procedure which every competent judge agrees you can always use, successfully, in finite time, to calculate every value of that function.



 

 An interesting fact occurred to me upon reading this.  According to linux "man 4 random",
       The  random  number  generator  gathers environmental noise from device
       drivers and other sources into an entropy  pool.   The  generator  also
       keeps  an  estimate of the number of bits of noise in the entropy pool.
       From this entropy pool random numbers are created.
These can be read from /dev/random in a computer program.  Thus, your desktop has a random oracle.

I've used it in combinatorial search to get wider coverage of the search space.

Martin Dowd


 

-----Original Message-----
From: Colin McLarty <colin.mclarty at case.edu>
To: Foundations of Mathematics <fom at cs.nyu.edu>
Sent: Fri, Aug 12, 2016 3:15 pm
Subject: Re: [FOM] Counterfactuals in relative computability theory





Church's Thesis would be shown false if someone exhibited a provably non-recursive function together with a procedure which every competent judge agrees you can always use, successfully, in finite time, to calculate every value of that function.


I am not waiting for this to happen.  But this is what it would be to show Church's Thesis is false.


Compare how people did, in fact, convince themselves that not every effective function is primitive recursive.



On Fri, Aug 12, 2016 at 5:18 AM,  <W.Taylor at math.canterbury.ac.nz> wrote:

Suddenly I am at sea.


you only mean them to be denials  of the
Church-Turing thesis or things implying that denial.


Obviously the above presupposes that CTT is something that is
either true or false.   I had assumed it was merely a convention
or definition of "computable" (natural-domained-)function.

Can someone please enlighten us as to how it could be false?

-- Bill Taylor


----------------------------------------------------------------
This message was sent using IMP, the Internet Messaging Program.

_______________________________________________
FOM mailing list
FOM at cs.nyu.edu
http://www.cs.nyu.edu/mailman/listinfo/fom




_______________________________________________
FOM mailing list
FOM at cs.nyu.edu
http://www.cs.nyu.edu/mailman/listinfo/fom


-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20160812/3514a784/attachment.html>