I think it is probably possible to block the result of universal realizability by tightening up our definition of computation. Certainly we ought to respect the fact that programmers and engineers regard it as a quirk of Turing's original definitions and not as a real feature of computation. Unpublished works by Brian Smith, Vinod Goel, and John Batali all suggest that a more realistic definition of computation will emphasize such features as the causal relations among program states, programmability and controllability of the mechanism, and situatedness in the real world.

John R. Searle: “Is the Brain a Digital Computer?

In which works did the authors mentioned by J. R. Searle present their “more realistic definitions of computation”? I searched for it, but if they're hidden in monographs, it will be difficult to find them.

  • Is Searle talking about the same problem that Chalmers discusses in "Does a Rock Implement Every Finite-State Automaton?", i.e. what counts as a physical instantiation of a given abstract computation?
    – Hypnosifl
    Aug 27, 2020 at 4:28
  • @Hypnosifl yes, that's the basic idea. Do you know a better definition of "computer" which avoids those difficulties?
    – viuser
    Sep 10, 2020 at 20:34

1 Answer 1


One should bear in mind that Searle writes a great deal about issues such as the relation between mind and brain, and the limits of artificial intelligence, and what these limits might tell us about that relation. He is not so much concerned with what is computable in completely abstract terms as with whether we can think of the brain as a computer, and if so, whether this has consequences for our understanding of minds. The issue of interpreting the significance of the Church-Turing thesis in this context is considerably more subtle than most accounts allow.

Firstly, Turing's use of 'computable' really answers to the concept of 'effectively computable'. The distinction may seem a fine one, but it potentially masks a misinterpretation of the Turing thesis. Copeland has a useful discussion of this point in section 2 of the SEP article on the Church-Turing thesis, and there are a number of references there to follow up.

Secondly, it is appropriate to impose a physical restriction on what counts as a computer. If we do not do so, there are any number of ways of specifying a hypercomputer, i.e. a computer that transcends the capabilities of a Turing machine. An analog neural network, for example, is capable of being a hypercomputer, but it would need to operate with arbitrarily fine precision. In our quantum universe, no such computer exists. So the definition of a computer has to be about physics and not just mathematics. Again, there are a number of useful references in the SEP article and in the Wikipedia article about hypercomputation.

Thirdly, it is problematic to explain how the Turing thesis applies to an interactive computer. A Turing machine is conventionally envisaged as a black box device, with an indefinitely long tape and a machine head that moves up and down reading and writing numbers onto the tape. Input to the machine takes the form of the initial state of the tape and its output is the final state. If an external agent writes onto the tape while a computation is in progress, then this violates the specification of a Turing machine. But this is in effect exactly what happens when a computer interacts with its surroundings. This has led some theorists, such as Peter Wegner and Dina Goldin, to claim that what they refer to as the strong Church-Turing thesis is false: it does not apply to interactive computers. (For example, see Goldin D., Wegner P. (2005) The Church-Turing Thesis: Breaking the Myth. In: Cooper S.B., Löwe B., Torenvliet L. (eds) New Computational Paradigms. CiE 2005. Lecture Notes in Computer Science, vol 3526. Springer, Berlin, Heidelberg.) Wegner and Goldin are not entirely 'mainstream' in their views, and for my part, I would be unwilling to say that the thesis is false, but we must be careful about interpreting its significance. At any given instant in time we could take all the interactive input that a computer has received, encode it in some way and include it on the input tape of some Turing machine. But an instant later, when the computer has received some more interactive input, we would have a different specification. The interactive computer is not a single Turing machine but a long sequence of Turing machines that evolves over time in accordance with the input it receives from whatever it interacts with. Without a complete specification of the portion of the universe that the computer is capable of interacting with, we cannot specify what future Turing machine it will evolve into. This suggests that the concept of computable functions has relatively little to tell us about the capabilities and limitations of artificial intelligences, or for that matter human beings.

  • okay… … again this answer doesn't address the question. It's not about if Searle is right, it's really a simple reference request: The definitions of computation by Brian Smith, Vinod Goel, and John Batali.
    – viuser
    May 9, 2018 at 18:57
  • 1
    "Unpublished" suggests that no references are available. Brian Smith has an interesting paper about computation available on Google Books here: books.google.co.uk/…
    – Bumble
    May 10, 2018 at 11:37
  • yeah, but maybe in the meantime they somehow published their definitions. If Searle said this this week, sure, there would be no point to ask.
    – viuser
    May 10, 2018 at 13:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.