Re: Penrose's Computing Pi Description?


"H. J. Sander Bruggink" <sanderbruggink@xxxxxxxxxxx> wrote in message
news:d8bvfr$q58$1@xxxxxxxxxxxxxxxxxxxxxxxxxxx
> Stephen Harris wrote:
>> "H. J. Sander Bruggink" wrote
>>>In the standard definition of a TM, it can only output things
>>>after it has finished. The "output" of a non-terminating TM
>>>is usually taken to be undefined.
>>>
>> Is that because it is assumed that the input is uncomputable?
>
> What do you mean by an input being uncomputable? I have heard
> about functions being uncomputable, but not about an input
> being uncomputable.
>
>

I provide a short quote below and extract a portion of it now:

"So we could imagine designing a programme that checks to see if
a given TM halts on a given input string. ... programme goes into an
infinite loop on a given input sequence). ... Now for some input TMs
and input strings this is very easy. If the TMs initial state is the halting
state, we know right away that the machine will halt for the input string."

SH: I think that means the input string is computable. There are some
input strings in which the machine will not halt. That means the input
is undecidable or uncomputable.

http://www.csee.umbc.edu/help/theory/computable.shtml#halting

"So we could imagine designing a programme that checks to see if a
given TM halts on a given input string. (Equivalently, since real-
computers are just physical implementations of TMs, this is the
same as writing a programme (in C or Java) that determines wether
a given (C or Java) programme goes into an infinite loop on a
given input sequence).

Now for some input TMs and input strings this is very easy. If
the TMs initial state is the halting state, we know right away
that the machine will halt for the input string .

The "Halting Problem" is a very strong, provably correct, statement
that no one will ever be able to write a computer program or design
a Turing machine that can determine if a arbitrary program will halt
(stop, exit) for a given input.

This is NOT saying that some programs or some Turing machines
can not be analyzed to determine that they, for example, always halt.

The Halting Problem says that no computer program or Turing machine
can determine if ALL computer programs or Turing machines will halt
or not halt on ALL inputs. To prove the Halting Problem is unsolvable
we will construct one program and one input for which there is no
computer program or Turing machine."
-------------------------------------------------------------------------------------

> H.J. : What do you mean by an input being uncomputable?

I mean that for a given TM, an input which halts is computable input.
I mean that conversely, for a given TM, an input which does not halt
is uncomputable. It is hopefully true that for a given TM, which
remains the same TM, that an input which halts and is computable
for that given TM, must be different that an input that does not
halt for that same TM. The different behavior would seem to be
caused by a difference between the inputs since the TM remains the
same, uncomputable non-halting input vs. computable halting input.
I am not quoting this to delve into the Halting Problem, per se, but
for a standard usage of "input", halting, undecidable, uncomputable.

http://cs.wwc.edu/~aabyan/Theory/Computable.html
"Due to the computational equivalence of formal systems to
other computational capability, we get the Halting problem,
the uncomputable numbers and other unsolvable problems."

http://www.j-paine.org/students/lectures/lect7/node19.html
"Turing used the halting problem to demonstrate that there are some
functions (or numbers) that one can describe but not compute."

> SH: How about for Pi? How about for the infinite many of
> irrationals produced by taking the square root of a prime?

H.J.: What do you mean with "what about Pi"? We are talking
about TMs and not about numbers, right?

SH: Not exactly. Pi is mentioned by Turing (1936) as a
computable number. That means there is an effective procedure
to compute its digital expansion which happens to be infinite.
I thought the discussion was about the correct description and
use of terms for explaining a particular effective procedure
which can only be unending, as a non-terminating entire process,
on an abstract logical computing machine, not a physical PC.

There are other numbers which are uncomputable, such as
truly random numbers, which exist, whether or not there is
an effective procedure or function to compute them. The TM
that computes Pi relies upon instructions, which I think of as
input. A TM is an abstract device which is used to clarify the
intuitive notion of an algorithm. The requirement for finiteness
is a logical necessity for defining a physical effective procedure.
I think Knuth's term "computational method" which relaxes the
requirement for finiteness but is otherwise exactly like an
algorithm is an appropriate abstract term for a abstract device.
He had a reason for inventing it. Musser also uses the term:

"Execution of steps may repeat other steps, so that although the set of
steps is finite, executions of them may produce an infinite sequence of
steps--finite termination is not a requirement (it is a requirement of the
generic algorithm concept). Nonterminating computational methods are useful,
...."

SH: To me the usage means the algorithm concept as a whole
is not seen to terminate, despite finite steps along the way. Penrose
uses the word algorithm to mean the algorithm finishes, so that
there is a series of algorithms completed rather than seeing the
overall process as algorithmic like = computational method.
Since Penrose is talking about computing Pi on a TM, then
he should use the theoretical, same abstract categorical level.

A physical computer cannot compute the unending digital
expansion of Pi because it runs out of physical resources,
whereas a TM has no such physical constraints (abstract).
The notion of Pi being computed unendingly belongs to a TM,
employing a "computational method" which matches a process
churning throughout eternity rather than within physical time.

--------------------------------------------------------------------------------

http://hebb.cis.uoguelph.ca/~skremer/Teaching/CIS4600/Lectures/27460/

The Halting Problem

"Now remember that our definition of a TM machine included
a special state ``h'' defined as the halting state. When the TM
reaches that state, it is done and it accepts the input string. We
can easily tell if a string is accepted, by simply giving it that
string. If the machine halts, we know the string is accepted.

But now suppose, we want to know if a string s is not accepted.
We could give the string to the TM, but we'd have to wait forever
before we could be certain that the string is not accepted.

So we could imagine designing a programme that checks to see
if a given TM halts on a given input string. (Equivalently, since
real-computers are just physical implementations of TMs, this is
the same as writing a programme (in C or Java) that determines
whether a given (C or Java) programme goes into an infinite loop
on a given input sequence).

Now for some input TMs and input strings this is very easy.
If the TMs initial state is the halting state, we know right away
that the machine will halt for the input string ."
-----------------------------------------------------------------------------------

Regards,
Stephen


.

Relevant Pages