OT: Church-Turing thesis (was Re: TCL can't do as much as Perl)

R. T. Wurth wrote:


Well, there's always the technical, trivial proof from Computer Science: either language can be used to simulate a Turing Machine (given underlying hardware with infinite memory), thus they are equally powerful, and no language can exist that is more powerful. Of course by this measure almost all modern, viable computer languages are equal.

Well, not quite. That they can both simulate a Turing machine is fine: they can both compute any function that can be computed by any other Turing machine (given enough memory). However, it is a further claim to state that "no language can exist that is more powerful". Firstly, the Church-Turing thesis is unproven (hence still a thesis, not a theorem), and unprovable. Secondly, the thesis states that a universal Turing machine (UTM) is able to compute any function which can be computed by an "effective method". An effective method is (informally) defined as being those tasks which an unaided human could in principle achieve, using just pencil and paper, following a finite number of instructions, in a finite number of steps, without using intuition etc. In particular, a machine could be capable of tasks which an unaided human could not perform, and thus would be strictly more powerful than a universal Turing machine. Conversely, human cognitive abilities may turn out to be more powerful than an UTM -- that "without using intuition" gives some wiggle room in the definition of "effective method".

There is little doubt that the Church-Turing thesis (about "effective methods") is true, whereas the stronger claim that this represents the capabilities of all possible physical machines is unknown. Likewise, the claim that no more powerful language can exist is also unknown. And that's just the closed world of mathematical functions -- there is also the issue of interaction with an environment, which most modern languages can do. Turing also defined "choice machines" which were Turing machines + interactive choice.

Personally, I think the stronger thesis (that all computable functions are computable by UTMs) is probably true, ignoring interaction. But this is a philosophical belief, not a result. To get back to the original discussion; that both languages can simulate an UTM indicates that they are both *at least* as powerful as an UTM, which is pretty powerful. I reckon Tcl wins on the interaction front, but again, that's a philosophical belief... :-)

-- Neil
.

Relevant Pages

  • Re: Recursive language which is not context-sensitive
    ... language which is not context-sensitive: ... sensitive Grammar G and build up a turing machine T which accepts the ... down the 37th context sensitive grammar. ... is just a garbage string? ...
    (sci.math)
  • Re: Raatikainens Paper on Chaitin
    ... >> just be equal to e, with a corresponding Turing machine M_e. ... it established, instead, that the powers of human reason could not be ... I repeat Penrose and compate it to * immediately above: ... Leibniz dream of universal language formally mathematically expressed. ...
    (sci.logic)
  • Re: Arthur ODwyer on the feasibility of simulating a Turing Machine
    ... > equivalent to Church's thesis re the Turing machine. ... that Marxists would attempt to get involved in mathematical philosophy. ... Initially writing represents speech, and it is very unusual to know how to ... However written language has its own ...
    (comp.programming)
  • Re: An uncomputability conjecture
    ... > language such as LISP or Prolog. ... > Turing machine that corresponds to R. ... let be the set of input words to ... we consider the possible uncomputability ...
    (comp.theory)
  • resolving Wills misunderstanding
    ... You don't even need the Godel number of UTM ... If the proof works in a language that is equivalent to the instructions ... and you can tell a TM to emulate another TM's ...
    (comp.theory)