[FOM] Counterfactuals in relative computability theory

[Kreinovich, Vladik]

Church-Turing thesis states that anything that can be computed on any physical device is recursive. While in modern physics, we have not yet found any physical process that can lead to computing a non-recursive function, one can imagine such processes -- and several papers have some hypothetical proposals of such processes. For example, if we allow infinite time and perfectly working time machine, we can compute non-recursive functions, e.g., we can check whether a Turing machine will halt or not -- by setting a time machine that will send a signal back if it halts.

I am not arguing that CTT is false now, with modern physics, but in principle, since physics changes, who knows, it may turns out to be false.
________________________________________
From: fom-bounces at cs.nyu.edu <fom-bounces at cs.nyu.edu> on behalf of W.Taylor at math.canterbury.ac.nz <W.Taylor at math.canterbury.ac.nz>
Sent: Friday, August 12, 2016 3:18 AM
To: fom at cs.nyu.edu
Subject: Re: [FOM] Counterfactuals in relative computability theory

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