Re: Computable functions/reals.

On 22 Aug, 00:19, reaste...@xxxxxxxxx wrote:
On Aug 21, 12:19 pm, ju...@xxxxxxxxxxxxx wrote:
On 21 Aug, 18:41, reaste...@xxxxxxxxx wrote:

Even an infinitley fast sequential computer
can't read every position of an infinite tape.

Why so? Rather, I'd think, it is your Zeno machine (as you define it
below) that does not straight conform to an "infinitely fast machine",
which sounds like it should be a machine that reads/writes the whole
tape in O(0), that is, "in no time at all".

Sure, why not.

Let our Zeno machine do the first operation
in 0 seconds, the second operation in 0 seconds, etc.
Now we can do an infinite number of operations
in 0 time. The result is still the same.
No sequential computer can read more
than a finite number of positions from the tape.

What is "time" here? The abstract machine goes through a succession of
states and the tape is really an input/ouput. The notion of "time"
belongs to "an outer environment", if it exists at all. Within such
given context, the machine you are defining is an "infinitely fast"
machine that performs operations "in no time": that is -- a fortiori,
as it seems the only reasonable consequence -- such machine, although
performing all steps one by one as usual, can read/write the whole
infinite input/output "at once" _within the reference time_, by its
very definition.

But, this is *not* saying a Zeno machine is an infinitely fast
machine! And so, despite this definition gives a kind of supremum for
the time taken, it is not in itself enough to assume that the machine
will actually ever perform *all* the operations! That's Zero's
paradox, and a way to say this definition is "sloppy".

It is easy to prove no sequential computer can ever
read "all" of an infinite tape.

To me your "proof" is flawed. More later.

The point maybe is: for a definition of a Zeno machine to even be
possible, we have first to accept we can define infinitely fast
machines, that is, as I'd put it, we allow machines that take O(0) or
"no time". Then a Zeno machine becomes a machine that "accelerates
contra-exponentially" (argh), up to "infinite speed" in, as we are
saying, 2 seconds.

We give the Zeno machine the description of a normal
TM and start the emulation. If the normal TM halts
the Zeno machine writes a "1" to output tape.
We wait 2 seconds and examine the output tape.
If the tape contains a "1" then the normal TM
halted, otherwise, the normal TM never halts.

With the revised definition, this becomes: in, at worst (and
*exactly*), two seconds, our Zeno machine does halt, with a 0/1 answer
telling whether the given TM halts or otherwise.

Our Zeno machine never halts (unless the TM it is
emulating halts).

Of course, I think this is inconsistent.

We have to halt it to examine what is on the tape.

And this is incorrect: either a machine halts or it doesn't; it is not
we halting it, at least not under the usual definitions. The Zeno
machine, as you have defined it, halts at worst after exactly two
seconds. To be specific, the worst case corresponds to simulating a TM
that does not halt.

BTW, Wikipedia says quite the opposite: among the Examples, they put
"The entire set of natural numbers is computable."

I prove this is incorrect.

To me, your proof is flawed. More below.

Consider the positions in our set S after we halt
the Zeno machine. Each of these positions
represent a natural number that is too large
to be read by a sequential computer.

Absurd mess, at least I think. For instance, TM and Zeno machine do
not share the same tape, so I do not even get what can be the point
here.

I should have been more specific.

Now it is indeed more clear.

The sets, S_i, are the unread positions on
the input tape being read by our simulated
TM after read number i.

I think you mean "after step number i". All machines we are dealing
with are in fact sequential machines.

Since the input tape is infinitely long,
no S_i can ever be the empty set.

Again, this is not the case. If you allow the tape to be infinitely
long, so actually allowing a potentially infinite input/output, then a
supposed infinitely fast machine will process the whole infinite input/
output in no time, by definition. I mean, if you put it down to
formulae, it is a matter of consistency.

The Zeno machine emulating the TM also never halts
unless a blank position is read from the input tape.

Then it is not an infinitely fats machine, rather it is a machine that
can accelerate without limit, but never get the infinite speed. Still
this definition is not sound. From the stand-point of an observer
(should I say, the chronometer), after 2 seconds your Zeno machine
*must* have stopped, so *all* positions of the ideal tape must have
been read, including the case there were no blanks at all. So such
Zeno machine, to have a sound definition in our reference model,
*must* get infinite speed on the worst case.

I might put it this way: there is no room for "weak infinities" into
the computable realm.

Assume no blank space is read from the input tape
by the simulated TM (the TM never halts).

Even if we wait until the Zeno machine has performed
an "infinite" number of operations (whether it takes
2 seconds, 0 seconds, or forever) there will be
a non-empty S_z that is a subset of all S_i.
S_z will contain natural numbers that can
never be read by any sequential computer.

Russell
- 2 many 2 count

What I glimpse is that your argument resounds Cantor's. That's, as I'd
put it, the worst disaster that can happen to computability.

Have a look at this list and I hope you'll "see", in the intuitive
sense, all combinations of dots and blanks must be covered by the very
idea of an infinite elaboration:

list(oo) :=
+0:(0)
+1:1(0)
+2:01(0)
+3:11(0)
+4:001(0)
+5:101(0)
...
---
...
-5:010(1)
-4:110(1)
-3:00(1)
-2:10(1)
-1:0(1)
-0:(1)

-LV
.

Relevant Pages

  • Re: Computable functions/reals.
    ... This tape may unary representation of a natural ... can't read every position of an infinite tape. ... Assume we have a universal Zeno machine that performs ... halted, otherwise, the normal TM never halts. ...
    (sci.logic)
  • Re: The Modified Halting Problem, Take ??? .
    ... Turing tapes" will not be a set or even a proper class in NAFL, ... each tape itself is an infinite entity. ... They're usually described as potentially infinite or finitely unbounded. ... and there is no last digit of Pi ever computed which one would think ...
    (sci.logic)
  • Re: The Modified Halting Problem, Take ??? .
    ... Turing tapes" will not be a set or even a proper class in NAFL, ... each tape itself is an infinite entity. ... They're usually described as potentially infinite or finitely unbounded. ... down or erasing binary digits one-at-a-time in the cells on a linear ...
    (sci.logic)
  • Re: turing completeness
    ... claim that the tape *must* be infinite. ... >>The Turing Machine just needs to be able at will to drive to CompUsa ... computer runs out of memory its operating system aborts the TM ...
    (comp.programming)
  • Re: Turing Machines and Physical Computation
    ... > So it must be bigger than any such size, and a tape ... an infinite tape is a TM that never halts due to undecidability. ... a finite number of digits. ...
    (comp.theory)
Quantcast