Re: Notions of computation

From: Suresh Venkat (suresh_at_research.att.com)
Date: 03/28/04 

Date: 28 Mar 2004 12:26:24 -0800

Laurie wrote:
---------------------------
Firstly, as everybody knows, there are multiple equivalent ways of
formalizing the same notion of computation: Turing machines, partial
recursive functions, lambda calculus, combinatory logic, etc. Of
these, Turing machines are the most popular expository tool for
discussing computability theory.
----------------------------

One possible reason for this is that most of the uniform complexity
classes are phrased in terms of resource constraints on a Turing
Machine, whether it be a time bounded, space bounded, or randomness
bounded class.

Relevant Pages

  • Re: Notions of computation
    ... > formalizing the same notion of computation: Turing machines, ... > recursive functions, lambda calculus, combinatory logic, etc. ... Step 1: Representation of tape. ...
    (comp.theory)
  • Notions of computation
    ... formalizing the same notion of computation: Turing machines, ... recursive functions, lambda calculus, combinatory logic, etc. ... basic facts as "the union of recursive languages is recursive" and "if ... one on that tape, and then these all tapes on this one tape" instead ...
    (comp.theory)
  • Re: A qn on primitive recursive functions
    ... > discussing recursive functions BEFORE we meet Turing machines, ... > course, remember, before we've heard of Turing machines, etc.] speculate ... > that the total recursive functions are ALL the intuitively computable ... then the diagonalization trick will necessarily generate ...
    (sci.logic)
  • Re: Computable functions/reals.
    ... abstraction or extension, IMHO, by the Church-Turing thesis. ... can extend Turing machines the way Mr. Ullrich or anyone else does. ... machines are intuively computable functions on N and all intuively ... all recursive functions on N are turing machines. ...
    (sci.logic)
  • Re: Computable functions/reals.
    ... When we are speaking about Turing machines some other posters say we ... functions on the naturals. ... some posters avoid that restriction to reintroduce it indirectly in ... essentially recursive functions on N by the literature, ...
    (sci.logic)