Re: Computable functions/reals.

On 18 elo, 23:54, "David C. Ullrich" <dullr...@xxxxxxxxxxx> wrote:
In article
<8d97856b-0c2b-4977-ae09-ac2979c2a...@xxxxxxxxxxxxxxxxxxxxxxxxxxx>,



Gc <Gcut...@xxxxxxxxxxx> wrote:
On 18 elo, 14:15, David C. Ullrich <dullr...@xxxxxxxxxxx> wrote:
On Sun, 17 Aug 2008 08:01:41 -0700 (PDT), Gc <Gcut...@xxxxxxxxxxx>
wrote:

On 17 elo, 17:57, Gc <Gcut...@xxxxxxxxxxx> wrote:
On 16 elo, 15:58, Frederick Williams <frederick.willia...@xxxxxxxxx>
wrote:

Gc wrote:

.... I`m just saying that we know exactly what the
computabole functions are,

Indeed so, but Bill Taylor is asking about and David Ullrich is
writing
about _something else_

there is now place for higher level of
abstraction or extension, IMHO, by the Church-Turing thesis.

The Church-Turing thesis (despite the fact that it's called a thesis)
is
a definition of what a computable function f : N --> N is. BT is
enquiring about what computable functions g : R --> R might be.

Your objection is a bit like say that a rational number is defined to
be
p/q for integers p, q=/=0 and therefore there is no such thing as a
irrational number. What _is_ the case is that however an irrational
number may be defined it is not going to be defined as p/q for
integers
p, q=/=0.

This is different. In every book about recursive functions f:N--->N it
is said that they calculate exactly the same stuff than the ordinary
Turing machines. I might be wrong, but to me it is not clear that we
can extend Turing machines the way Mr. Ullrich or anyone else does.

You really have no idea what a _definition_ is?

The Church-Turing thesis is NOT an definition.

I was referring to the definition of "computable function
from R to R".



It says what the
actually computable functions are. The way you use something
resembling Turing machines in your definition is nonsense in a way
that you take all these infinite tapes with infinite many blanks and
non-recursively enumable languages an lose all the idea behind Turing
machines. The Turing machine with tapes and heads is actually sort of
aide to intuition and a metaphor and not the abstract machine itself,
which contain NO tape. So be carefull when you play with metaphors
instead of actual rigorous mathematical definitions.
Secondly I give in when you say that your definition of "computable"
functions on R, is not actual computation, instead it is a definition
of something else.

Because extending recursive functions (which are from computational
view "essentially" same than the Turing machines) indeed they are
trying to do, no matter what they try to claim.

And this is also what contradicts the Church-Turing thesis, because we
are not talking about the same Turing machines anymore.

You're really starting to seem dense.

Look. The definition I've proposed for "computable
function from R to R" cannot possibly contradict
the CT thesis, because it talks about something
else.

It does right when you say that those functions are "computable".

Jesus. I can't decide whether you're just not paying
attention or trolling or what.

Look at the following text. The _whole_ text, not
just part of it. The start and end are marked with
"<text>" and "</text>"

<text>

Definition: A function f : N -> N is recursive if
f(n+1) = f(n) for all n in N.

Theorem. If f : N -> N is recursive then f(3) = f(1).
Proof. f(3) = f(2+1) = f(2) = f(1+1) = f(1). QED.

</text>

Question: Is that text valid mathematics?

Answer: Yes. If you think there's something incorrect
about that text you don't understand what a definition
is.

(Of course it's _incredibly_ badly written mathematics;
that's a different question.)

Question: Note that the Theorem is true. Is it true
that if f is any recursive function then f(3) = f(1)?

Answer: Of course not.

Question: Does the definition of "recursive" in the
text contradict the CT thesis?

Answer: No.

I don`t understand you at all. If the CT- thesis is that ALL turing
machines are intuively computable functions on N and all intuively
computable functions on N are turing machines. Then if we have a
theorem that all turing machines are recursive functions on N and that
all recursive functions on N are turing machines. Then if you say that
all intuively computable functions are not recursive functions on N,
then what?





_If_ I were proposing a definition of "computable
function from N to N" that was not equivalent to
the standard definition then _that_ would contradict
the CT thesis.

David C. Ullrich

"Understanding Godel isn't about following his formal proof.
That would make a mockery of everything Godel was up to."
(John Jones, "My talk about Godel to the post-grads."
in sci.logic.)

--
David C. Ullrich

.

Relevant Pages

  • Re: Computable functions/reals.
    ... 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. ... That would make a mockery of everything Godel was up to." ...
    (sci.logic)
  • Re: Computable functions/reals.
    ... in terms of Turing machines. ... than computable functions, and his paper is rather muddled but made much ... Nobody is talking about "right choices" in what you ... functions and the notion of computability in general: ...
    (sci.logic)
  • 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.
    ... 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)
Quantcast