Poll: Are PCs Turing Machines?
Eray Ozkural exa
Are PCs physical examples to Turing Machines? [*]
Please write only Yes/No to avoid discussion.
Regards,
--
Eray
[*] The alternative being they are not. There are some arguments that
this is the case.
oğin
>
> Please write only Yes/No to avoid discussion.
No.
Peter Douglass
news:320e992a.0412...@posting.google.com...
>I wonder what people really think about this.
>
> Are PCs physical examples to Turing Machines? [*]
>
> Please write only Yes/No to avoid discussion.
no
Rick Decker
Eray Ozkural exa wrote:
> I wonder what people really think about this.
>
> Are PCs physical examples to Turing Machines? [*]
>
Even if you change "to" to "of" the answer is no.
Regards,
Rick
George Cox
>
> I wonder what people really think about this.
>
> Are PCs physical examples to Turing Machines? [*]
No.
Will Twentyman
No, they are not Turing Machines.
--
Will Twentyman
email: wtwentyman at copper dot net
sirix
What the hell... yes?
sirix.
oğin
:-)
Dave Vandervies
Eray Ozkural exa <exama...@gmail.com> wrote:
>I wonder what people really think about this.
>
>Are PCs physical examples to Turing Machines? [*]
>
>Please write only Yes/No to avoid discussion.
Yes, conditionally: You need access to an unbounded supply of removable
media.
dave
--
Dave Vandervies dj3v...@csclub.uwaterloo.ca
I think at this point I can use the term "idiots" without fear of
being accused of libel.
--seebs
mike3
news:320e992a.0412...@posting.google.com...
No.
Richard Brown
wrote:
>I wonder what people really think about this.
>
>Are PCs physical examples to Turing Machines? [*]
>
>Please write only Yes/No to avoid discussion.
>
>Regards,
No
George Cox
PCs have physical limitations that TMs do not have. There can be _no_
physical examples of TMs.
George Cox
>
> In article <320e992a.0412...@posting.google.com>,
> Eray Ozkural exa <exama...@gmail.com> wrote:
> >I wonder what people really think about this.
> >
> >Are PCs physical examples to Turing Machines? [*]
> >
> >Please write only Yes/No to avoid discussion.
>
> Yes, conditionally: You need access to an unbounded supply of removable
> media.
There is no such thing as "an unbounded supply of removable media."
Also note that removable media require a person to remove them, so that
goes beyond a PC.
ste...@nomail.com
You could have a robot replace the media. Robotic tape drive
systems exist. Of course they usually have a very limited
supply of removable media. Of course your average PC
does not have such a robotic system attached to it.
Stephen
Richard Henry
"Eray Ozkural exa" <exama...@gmail.com> wrote in message
news:320e992a.0412...@posting.google.com...
> I wonder what people really think about this.
>
> Are PCs physical examples to Turing Machines? [*]
>
> Please write only Yes/No to avoid discussion.
>
No.
Do they have an infinite tape?
Bill Dubuque
>
> I wonder what people really think about this.
>
> Are PCs physical examples to Turing Machines? [*]
You may be interested in my prior post which
discusses work on Turing style analyses of
physically realizable computing devices. See
http://google.com/groups?selm=y8zel227tyr.fsf%40nestle.ai.mit.edu
Here "physically realizable" means the machines are
constrained by hypothesized laws of physics, which
in Gandy's work happens to be ATOMISM and RELATIVITY.
Follow the above link for further detail and references.
--Bill Dubuque
Kent Paul Dolan
> I wonder what people really think about this.
> Are PCs physical examples to Turing Machines? [*]
> Please write only Yes/No to avoid discussion.
Another moronic troll from Eray. Told point blank
that PCs are _not_ Turing machines because they
don't support infinite tapes, he's trying to alter
reality to fit his uneducated version of things
and his bogus argument repudiated by every educated
participant, with a _vote_.
Herc is also _exactly_ this stupid, tried the same
trick not long ago.
At least we have a measure of the level to which
Eray is willing to lower himself: at least as low as
Herc. It's not really possible to go lower without
posting a pyramid scam.
Clue, Eray: reality isn't subject to a vote, it just
_is_, whatever your opinions pro or con.
xanthian.
--
Posted via Mailgate.ORG Server - http://www.Mailgate.ORG
exama...@gmail.com
Eray Ozkural exa
> I wonder what people really think about this.
>
> Are PCs physical examples to Turing Machines? [*]
>
> Please write only Yes/No to avoid discussion.
A clarification is in order.
As far as I can understand from the replies, there are alternative
readings of my question, which is imprecision on my part.
We usually consider equivalence in computability to be a sufficient
condition for being a physical example to a model of computation,
essentially covering the capabilities of "causal mechanism" involved.
Therefore, we don't seek a 1-1 correspondence between
intuitively-simple physical states and storage/transition mechanism
and some common depiction of TM which involves a one-dimensional tape,
a single head etc. We seek a 1-1 correspondence with the abstract
definitions of state, tape and transition function that are fairly
independent of physical structure. That is, we do not require the
"physical example" to be a "physical example" of that rather odd
machine that we sometimes use to visualize what a TM could be like.
[*] Otherwise, the answer would be trivially no, and there would be no
need for a poll.
It may be regarded sufficient that we can find a TM counterpart to
everything essential to computation in a PC, and the other way around.
The most common objection is that a PC lacks an "infinite tape", while
many computer scientists suggest that the TM tape is unbounded, not
infinite, for the infinite portion of the tape consists entirely of
blank symbols. And that is probably an important point worth
considering in giving your reply, while other points are obviously
considerable.
I also gave an argument (Lambda Calculus and Turing Equivalence) that
replying no should necessarily imply that there are no physical
counterparts to lambda-calculus, cellular automata, etc. if we were to
believe that these guys are Turing equivalent. Considering this
argument might be a good way to think about the question.
Regards,
--
Eray Ozkural
[*] So, you can think each of various I/O channels in your PC to be an
additional tape, etc. and other modifications which do not change the
computing power of a TM.
Luis A. Rodriguez
> In comp.theory George Cox <george_...@spambtinternet.com.invalid> wrote:
> : Dave Vandervies wrote:
> :>
> :> In article <320e992a.0412...@posting.google.com>,
> :> Eray Ozkural exa <exama...@gmail.com> wrote:
> :> >I wonder what people really think about this.
> :> >
> :> >Are PCs physical examples to Turing Machines? [*]
Yes. They are physical EXAMPLES of Turing Machines, that is: The
HUMAN use of a theoretical T.M. can be reproduced with a PC. (And with
advantages because a human could not take notice of a halting
problem).
Thomas A. Li
sense.
Precisely, PC is a physical realization of a Turing machine with physical
limitation.
Turing machine is a mathematical model/abstraction of general computation,
including PC.
a PC can approach to a Turing machine closer and closer , but never be the
same, because the TAPE of a Turing machine is infinite. Given sufficient
storage, in our physical world, they are equivalent in computability.
Thomas Li
"Eray Ozkural exa" <exama...@gmail.com> wrote in message
news:320e992a.0412...@posting.google.com...
oğin
Mark Nudelman
> exama...@gmail.com (Eray Ozkural exa) wrote in message
> news:<320e992a.0412...@posting.google.com>...
>> I wonder what people really think about this.
>>
>> Are PCs physical examples to Turing Machines? [*]
>>
>> Please write only Yes/No to avoid discussion.
>
> A clarification is in order.
> We usually consider equivalence in computability to be a sufficient
> condition for being a physical example to a model of computation,
> essentially covering the capabilities of "causal mechanism" involved.
> It may be regarded sufficient that we can find a TM counterpart to
> everything essential to computation in a PC, and the other way around.
Still "no".
A TM can perform a calculation that requires 10^1000 storage cells, but no
PC or any other physical computer could do that.
--Mark
Lord of Chaos(Suresh Devanathan)
"oğin" <oği...@ragnarok.com> wrote in message
news:mdKdnWlEXNJ...@whidbeytel.com...
Lord of Chaos(Suresh Devanathan)
real live people.
Will Twentyman
> exama...@gmail.com (Eray Ozkural exa) wrote in message news:<320e992a.0412...@posting.google.com>...
>
>>I wonder what people really think about this.
>>
>>Are PCs physical examples to Turing Machines? [*]
>>
>>Please write only Yes/No to avoid discussion.
>
>
> A clarification is in order.
>
> As far as I can understand from the replies, there are alternative
> readings of my question, which is imprecision on my part.
>
> We usually consider equivalence in computability to be a sufficient
> condition for being a physical example to a model of computation,
> essentially covering the capabilities of "causal mechanism" involved.
The problem is that a TM does not have limits on the size of the data it
works with, as long as it remains finite. *EVERY* PC has a limit on the
data it can process. The abstract notion of a PC is equivalent to a TM,
but we have no abstract PCs, just the real deal with their limitations.
The issue is simple: a PC cannot handle *all* the data a TM can process.
Raffaello Galli
> I wonder what people really think about this.
>
> Are PCs physical examples to Turing Machines? [*]
>
> Please write only Yes/No to avoid discussion.
No.
Mitch Harris
>
> Given a PC. Is it computationally equivalent to *a* Turing Machine?
Do you mean (trying to restate the obvious) that "is there some TM
that computes the same things computable by a given PC?". Yes, of course.
Of course, there's also a DFA that does the same, because the PC has
a finite amount of memory, and that can be simulated by the
appropriate (humongous) number of states.
There doesn't seem to be any philosophical difficulties here at all.
--
Mitch Harris
(remove q to reply)
Eray Ozkural exa
Hi Mark,
There is another reading comprehension problem involved. Wearing the
philosopher hat, I think I should have made this one clear as well:
I do not ask the following:
Is the set of all PCs computationally equivalent to the set of all TMs
(whatever that means)
I ask:
Given a PC. Is it computationally equivalent to *a* Turing Machine?
That's a completely different question. I suggest you to consider the
latter reading, which is the correct reading.
Regards,
--
Eray Ozkural
oğin
> condition for being a physical example to a model of computation,
> essentially covering the capabilities of "causal mechanism" involved.
There is no equivalence in computability between a PC (or any other physical
computer) and a TM. So the answer is still (drum roll please) 'NO'.
ste...@nomail.com
: Eray Ozkural exa wrote:
:> Given a PC. Is it computationally equivalent to *a* Turing Machine?
: No. Any TM can accept arbitrarily large input. A PC cannot.
There is still some ambiguity here. For a given PC there is a Turing
Machine that computes all the functions the PC does. A TM can accept
arbitrarily large input but it can also ignore input that exceeds
some fixed bound. There is a TM that can compute x^2 for all all x.
A PC can only compute x^2 for all x <= M. There is also a TM that can
only compute x^2 for all x <= M. There is no PC that can compute x^2 for
all x.
Stephen
Will Twentyman
No. Any TM can accept arbitrarily large input. A PC cannot.
> That's a completely different question. I suggest you to consider the
> latter reading, which is the correct reading.
That is not even close to how I read the original question.
Stephen Harris
"Mitch Harris" <har...@tcs.inf.tu-dresden.de> wrote in message
news:31b2d2F...@news.dfncis.de...
> Eray Ozkural exa wrote:
> >
>> Given a PC. Is it computationally equivalent to *a* Turing Machine?
>
> Do you mean (trying to restate the obvious) that "is there some TM that
> computes the same things computable by a given PC?". Yes, of course.
>
No, he means can a PC always compute what a TM can compute.
IOW, he thinks that a PC can compute the same number of digits of Pi
as a TM, no matter how many finite digits of expansion are specified.
I'll put it this way. What I stated is his position. The question he asked
does not call for an answer that supports his position. The question
that he should have asked, because an affirmative supports his position is,
Given a Turing Machine. Is it computationally equivalent to *a* PC?
This is the converse of how he posed the question, and I think you
will agree the answer is No, of course. Because there are more
TM descriptions than a PC can achieve because of its limited memory.
Which means for each instance of a completion of a computable
operation by a PC, yes there is a TM which matches it. But not the
other way around, there are more TMs than have matching PCs.
I don't think Eray realizes the questions are not the same and have
opposing answers. He is thinking of an exact, one-to-one match
with no leftovers in both directions of comparison. I think isomorphic
is the word.
Thunderbird,
Stephen
bri...@encompasserve.org
> Eray Ozkural exa wrote:
>> Given a PC. Is it computationally equivalent to *a* Turing Machine?
>
> No. Any TM can accept arbitrarily large input. A PC cannot.
The one state TM that halts on step 1 cannot accept arbitrarily
large input.
Alternatively, putting my PC beside an arbitrarily large heap of
DLT cartridges and never hitting the ON switch counts as using that
entire heap as input.
Either some TM's cannot or all PC's can.
John Briggs
Herman Jurjus
> I wonder what people really think about this.
>
> Are PCs physical examples to Turing Machines? [*]
>
> Please write only Yes/No to avoid discussion.
Yes/No
Stephen Harris
"Will Twentyman" <wtwen...@read.my.sig> wrote in message
news:41b08...@newsfeed.slurp.net...
There is always a TM description to match up with a PC.
The answer is yes, but does not support Eray's position,
because he said the "other way around" also.
>>>>It may be regarded sufficient that we can find a TM counterpart to
>>>>everything essential to computation in a PC, and the other way around
There is not always a PC to match a TM description. The converse,
the other way around is not true. Eray doesn't grasp this. There are
more potential TMs than matching PCs.
>> That's a completely different question. I suggest you to consider the
>> latter reading, which is the correct reading.
>
> That is not even close to how I read the original question.
>
which was: >>>>>Are PCs physical examples to Turing Machines? [*]
No they are not because his question is about _all_ TMs.
There are more tms than pcs.
When Eray rephrased his question he changed the meaning:
>> Given a PC. Is it computationally equivalent to *a* Turing Machine?
There is still some confusion in his phrasing. But you notice he
has changed [all] "Turing machines" to "*a* Turing Machine"
The answer to this is more like yes, because there is always "a"
turing machine that can map to a PC.
But this rephrase which may change the emphasis of intepretation
does not help Eray's overall argument. "and the other way around"
Because there is not always a PC than can map to a TM. And that
is due to the TM/tape and the PC/memory having unequal potential
for completing finite computations.
Eray has a fragile ego and is looking for a way to escape the
appearance of an uneducated, non compus* mentis deviant. I predict
him next to say that since there is an overlap between what PCs and TMs
can compute (in terms of "short" finite executions to solving some problems)
>> Given a PC. Is it computationally equivalent to *a* Turing Machine?
which has been mentioned by the peanut gallery right along; that this
is all he meant by 'PCs are physical TMs'. Pretty much to reverse his
position as he did the meanings of his question and then conveniently drop
the "and the other way around". OTOH, he is arrogantly stupid and may
persist in making clueless remarks perhaps because he enjoys ridicule.
> --
> Will Twentyman
> email: wtwentyman at copper dot net
>
*o,
Stephen
Dave Vandervies
Don't you mean "only Yes/No to avoid discussion."?
dave
--
Dave Vandervies dj3v...@csclub.uwaterloo.ca
[user@localhost user]$ gcc -Wextra-push-over-the-cliff -o sample sample.c
sample.c:12: warning: this program appears to be a pointless exercise
--Ian Pilcher in comp.lang.c
Bill Dubuque
>
> There is a TM that can compute x^2 for all all x.
> A PC can only compute x^2 for all x <= M.
> There is also a TM that can only compute x^2 for all x <= M.
> There is no PC that can compute x^2 for all x.
Any physically realizable computer is a finite state machine (FSM).
FSMs can add arbitrary integers, but not multiply arbitrary integers
(not even square them, e.g. see Exercise 2-14 of H. Rogers, Theory of
Recursive Functions and Effective Computability). See also my prior post
http://google.com/groups?selm=y8zlo3gmqt0.fsf_-_%40berne.ai.mit.edu
--Bill Dubuque
Mark Nudelman
Well, when you said
>>> It may be regarded sufficient that we can find a TM counterpart to
>>> everything essential to computation in a PC, and the other way
>>> around.
the phrase "and the other way around" pretty much precludes the
interpretation that you're now proposing.
But if you're now asking, for each PC, is there a compuatationally
equivalent TM, then the answer is yes.
If you're asking, for each TM, is there a computationally equivalent PC, the
answer is no.
--Mark
Stephen Harris
Hi,
I have noted your perspicacious remarks. I think the finiteness
of matter is tied to the physical constraint on memory of a PC.
But the older theory which preceded the Big Bang, Steady State says:
At first glance this seems to imply we must abandon the idea that the
Universe could be unchanging. However this is not necessarily so, because of
one rather exceptional kind of expansion that can occur if the Einstein
Field Equations are modified appropriately. This is when the Universe is
always expanding, but the rate of expansion and the density of matter are
always the same. Clearly this
requires a continuous creation of matter to keep the density constant while
the Universe continually expands. Such a universe is called a Steady State
Universe . For many people this is an attractive possibility, because an
unchanging Universe is thought to be "more perfect" than a changing one
[79]. However this model cannot explain evidence obtained from optical and
radio telescopes that there was a higher density of radio sources and
quasars in the past than at present (the densities would have to be
unchanging, if the Universe were in a steady state, for then conditions
would be the same everywhere); and it does not give a natural explanation of
the cosmic background radiation (discussed below). It has therefore been
abandoned by almost all cosmologists.
SH: In the present theory, Big Bang, the density remains the same, and heat
death eventually stops any conversion of energy to mass. There is
experimental evidence that the Big Bang theory is true, while the older
conjecture of the Steady State universe of newly created matter was such a
small amount that it could not be detected by physical experiment to provide
evidence for the SST.
That is why I told Eray he would need a Nobel prize in order to plausibly
advance his notion that there is an unlimited supply of matter to store the
ever greater calculations of a PC so there is some sort of equivalence to an
unlimited tape, both capable of ever greater finite computation.
This made me think that there is another aspect of the TM which is
non-physical, dealing with time. Suppose there is newly created matter which
can be utilized by the physical PC. How could a physical calculation proceed
in a coherent manner when the best physical speed of operation would be the
speed of light. Also, besides the idea of the universe expanding forever,
providing new matter/memory if we adopt SST, is the factor that the
expansion is also supposed to accelerating. Which means there is no physical
way for the physical calculating signal to connect to newly created matter
in the universe which is going accelerated expansion away from our galaxy. I
think this is basically the same idea that light which travels at a finite
speed will never reach us from accelerated expanded region of the universe
even if the light travels from that region an infinite length of time.
I decided to run this musing by you just in case my physics was mistaken and
because I thought you might enjoy further speculation on physical
constraints which distinguish an abstract TM from a physical PC.
Best regards, Stephen
Eray Ozkural exa
> >> Given a PC. Is it computationally equivalent to *a* Turing Machine?
>
> There is still some confusion in his phrasing. But you notice he
> has changed [all] "Turing machines" to "*a* Turing Machine"
>
> The answer to this is more like yes, because there is always "a"
I didn't change the meaning. You failed to understand what is meant by
i) physical example
ii) the other way around
The universal quantifier has never been my intention.
That is, I think you have a reading comprehension problem.
The above is additional material which has tangential relevance.
-------------------------------------------------------
See also what I have said about counterfactual predictions of TM
theory, and nomologically possible worlds. Turing's theory is
concerned with physically similar possible worlds, it is indeed a
metaphysical theory, but there are sensible ways to understand it.
Stephen Harris
"Lord of Chaos(Suresh Devanathan)" <ida...@yahoo.com> wrote in message
news:319g2gF...@individual.net...
> dont ask stupid question to stupid people. get intelligent friends. meet
> real live people.
There is a basic problem with wormholes as a communication system.
Wormholes, as described by the equations of general relativity, are
dismayingly unstable. In fact, any wormhole connection that happens
to form between two points in space should pinch closed again so
rapidly that neither material objects nor light-beam messages can pass
across the wormhole "bridge" during its brief existence.
There can be no trust without a foundation of honesty which is MIA.
HERC777
Can a Nintendo plot weather charts 5 days ahead?
Cyberspace will be closer to a real TM, a billionfold memory increase
should really KiCK!
Herc
max
> I wonder what people really think about this.
>
> Are PCs physical examples to Turing Machines? [*]
>
> Please write only Yes/No to avoid discussion.
>
>
> --
> Eray
>
> [*] The alternative being they are not. There are some arguments that
> this is the case.
The PC is the control part of the TM, with an embedded limited tape.
In this sense it is equivalent, otherwise the questions is just "can you
physically have infinite memory?" And the answer is no as we are limited
by physics (can the world store an infinite amout of information? No)
A TM is a mathematical abstraction to derive analytically properties of
computational systems. So the question is a bit irrelevant (note as well
that if it is a PC or a MAC or a Cray or your brain the answer is the same)
Massimo
Edward G. Nilges
>
> Are PCs physical examples to Turing Machines? [*]
>
> Please write only Yes/No to avoid discussion.
>
> Regards,
This is an ignorant poll.
First of all, like Clinton, you have to parse "is" as he did when he
famously analyzed what it might mean to say a blowjob is sex...in
order to protect his wife, his daughter, Monica and the Presidency
from calumny, like a man.
A PC can SIMULATE a Turing Machine. A toaster, unless it is one of
those expensive toasters with an embedded chip, cannot simulate a
Turing Machine.
"Ability to simulate a Turing Machine" is a key idea in computer
science, and programmers who fail to understand it are in my
experience usually incompetent.
This damn "poll" gives equal credibility to an ignorant view: that a
Turing Machine exists ideally in Platonic heaven and can't even be
"simulated", a view that results in the equation of HTML with Fortran
and other Turing complete languages.
And it's typical that discussion be banned here. "Don't Make Me Think"
is not only the name of a computer book, it is the slogan of the New
Era.
Michael N. Christoff
>
> Are PCs physical examples to Turing Machines? [*]
>
> Please write only Yes/No to avoid discussion.
>
> Regards,
>
No.
l8r, Mike N. Christoff
Luis A. Rodriguez
> Eray Ozkural exa wrote:
> > Are PCs physical examples to Turing Machines? [*]
> A TM is a mathematical abstraction to derive analytically properties of
> computational systems. So the question is a bit irrelevant (note as well
> that if it is a PC or a MAC or a Cray or your brain the answer is the same)
> Massimo
Perfectly in accord !
Besides, during the handling a TM problem a human brain can be
confused, forgetful, tired etc. But a computer simulation most
probably not.
The condition of having an ilimited quantity of tape is a conceptual
question that is managed by the mathematician's brain not by the
Turing Machine itself.
Ludovicus
Luis A. Rodriguez
> "Mark Nudelman" <ma...@greenwoodsoftware.com> wrote in message news:<BCKrd.600129$mD.87873@attbi_s02>...
> > Eray Ozkural exa wrote:
> > A TM can perform a calculation that requires 10^1000 storage cells, but no
> > PC or any other physical computer could do that.
Absurd!! This is the same wrong concept that many people has of what
a TM is.
The TM dont'n "perform calculations", is the mathematician who
decides what a TM will do if it receives the input X = 10^10000, and
this can be easily simulated by a PC that can handle powers and
logarithms.
But if the process is chaotic,no mathematician, no TM , nobody can
calculate the result.
Ludovicus
peter_douglass
"Edward G. Nilges"
> A PC can SIMULATE a Turing Machine. A toaster, unless it is one of
> those expensive toasters with an embedded chip, cannot simulate a
> Turing Machine.
Let TM0 be the identity Turing Machine whose start state is its stop state,
and which has no legal state transitions. If we are only interested in
functional equivalence, we may "optimize" away features which are
unnecessary for obtaining correct results. For TM0, such unneccessary
features include the ability to read from the tape, write to the tape, and
move the head. We find that any toaster, even one without an embedded
chip, can in that way simulate TM0, provided we do not put the
input tape *into* the toaster ;-)
--PeterD
Henry
I have another point. Nothing can simulate a Turing Machine on earth
in the most rigorous sense. We need to have the ability that when we
run out of the tape, we can add more tape. When our machine cannot
locate certain amount of tape, we need to build a different version of
machine to continue the work assignment. When our machine cannot deal
with 10^100 different states and we have to do that, we want to order
a new machine to deal with 10^1000 different states. With this
capability in hand we have a Turing Machine.
Eray Ozkural exa
> Turing Machine exists ideally in Platonic heaven and can't even be
> "simulated", a view that results in the equation of HTML with Fortran
> and other Turing complete languages.
No, it has never been my intention to give any credibility to
Platonism. It's others that do it, and some of them are not even aware
that they do.
Cheers,
--
Eray
Mark Nudelman
> exama...@gmail.com (Eray Ozkural exa) wrote in message
> news:<320e992a.04120...@posting.google.com>...
>> "Mark Nudelman" <ma...@greenwoodsoftware.com> wrote in message
>> news:<BCKrd.600129$mD.87873@attbi_s02>...
>>> Eray Ozkural exa wrote:
>
>>> A TM can perform a calculation that requires 10^1000 storage cells,
>>> but no PC or any other physical computer could do that.
>
> Absurd!! This is the same wrong concept that many people has of what
> a TM is.
> The TM dont'n "perform calculations", is the mathematician who
> decides what a TM will do if it receives the input X = 10^10000, and
> this can be easily simulated by a PC that can handle powers and
> logarithms.
I didn't say that a PC couldn't handle an input of X=10^1000. I said that
it couldn't perform a calculation that requires 10^1000 _storage cells_.
(For example, multiplying two numbers, each of which has 10^1000 digits.)
There isn't enough matter in the universe to even begin to build a computer
that could hold a 10^1000 digit number.
--Mark
Mike
> > Are PCs physical examples to Turing Machines? [*]
> >
> > Please write only Yes/No to avoid discussion.
>
Yes
Luis A. Rodriguez
When a conceptual machine has calculated two numbers of 10^1000
digits or handled a matrix of 10^500 x 10^500 ?
Ludovicus
John Schoenfeld
> I wonder what people really think about this.
>
>
> Please write only Yes/No to avoid discussion.
>
Turing machines violate conservation of energy.
Bill Dubuque
><george_...@spambtinternet.com.invalid> wrote:
>:Dave Vandervies wrote:
>:>Eray Ozkural exa <exama...@gmail.com> wrote:
>:>> I wonder what people really think about this.
>:>>
>:>> Are PCs physical examples to Turing Machines? [*]
>:>>
>:>> Please write only Yes/No to avoid discussion.
>:> Yes, conditionally: You need access to an unbounded supply
>:> of removable media.
>
>: There is no such thing as "an unbounded supply of removable media."
>: Also note that removable media require a person to remove them,
>: so that goes beyond a PC.
>
> You could have a robot replace the media. Robotic tape drive
> systems exist. Of course they usually have a very limited
> supply of removable media. Of course your average PC
> does not have such a robotic system attached to it.
And what would replace the robot when it exhausts its preprogrammed
means of extending storage? And please tell us your algorithm for
harvesting more resources from the universe once you've depleted
Earth's resources... Of course we humans can employ our *ingenuity*
to devise stronger and stronger techniques for computing with larger
integers. They might involve advances in computer hardware, or more
efficient notations for working with larger integers, etc. But these
techniques are not *mechanical* because they depend upon the use of
human *ingenuity*. The concept which Turing sought to capture is
that of purely *mechanical* computation, the step-by-step execution
of instructions in a purely rote manner, i.e. without employing any
human intuition (e.g. meta-level reflection on the computation).
As we know now, Turing succeeded in isolating a very useful set of
functions, the recursive functions. Amazingly, every future attempt
at capturing such a notion of computability has led to precisely
the same class of functions, whether it be via lambda-calculus,
Post systems, Markov algorithms, combinatory logic, etc. etc; cf.
Church-Turing thesis http://wikipedia.org/wiki/Church-Turing_thesis
There is no known algorithm for constructing unbounded storage.
Hence physically realizable computers are finite-state machines
and are subject to their limitations, e.g. they cannot square
or multiple arbitrary length integers.
--Bill Dubuque
Stephen Harris
"John Schoenfeld" <j.scho...@programmer.net> wrote in message
news:a98beaaa.04120...@posting.google.com...
Conservation of energy applies to the physical universe
which is why a TM is not physical, but an abstract idea.
Luis A. Rodriguez
> I have another point. Nothing can simulate a Turing Machine on earth
> in the most rigorous sense. We need to have the ability that when we
> run out of the tape, we can add more tape. When our machine cannot
> locate certain amount of tape, we need to build a different version of
> machine to continue the work assignment. When our machine cannot deal
> with 10^100 different states and we have to do that, we want to order
> a new machine to deal with 10^1000 different states. With this
> capability in hand we have a Turing Machine.
Nonsense.
A Turing Machine is only a theory in the brains of mathematicians.
And a brain have not tapes.But the principle of infinite induction can
be programed.
If a Turing Machine is subject to rigorous logic it can, by the
defintion of Formal Logic, be simulated by a computer. 10^100
different states is a concept in the brain of a mathematician. No TM,
no machine, no brain can PROCESS 10^100 states, but for example, a
program that handles theorems can demonstrate that for m>2 the number
N = m^m + m! -1 cannot be prime for N < 10^27000000.
Ludovicus
Stephen Harris
"Luis A. Rodriguez" <lui...@yahoo.com> wrote in message
news:c9ba0a0b.04120...@posting.google.com...
> xyzw...@yahoo.com (Henry) wrote > >
>>
>> I have another point. Nothing can simulate a Turing Machine on earth
>> in the most rigorous sense. We need to have the ability that when we
>> run out of the tape, we can add more tape. When our machine cannot
>> locate certain amount of tape, we need to build a different version of
>> machine to continue the work assignment. When our machine cannot deal
>> with 10^100 different states and we have to do that, we want to order
>> a new machine to deal with 10^1000 different states. With this
>> capability in hand we have a Turing Machine.
>
> Nonsense.
> A Turing Machine is only a theory in the brains of mathematicians.
> And a brain have not tapes.But the principle of infinite induction can
> be programed.
The theory of relativity is a theory in the brains of physicists.
And a brain does not have relatives.
Sound stupid? Just like your kindergarten argument.
Drop some more acid, lamebrain.
André Betz
Eray Ozkural exa
> Eray Ozkural exa wrote:
>
> > exama...@gmail.com (Eray Ozkural exa) wrote in message news:<320e992a.0412...@posting.google.com>...
> >
> >>I wonder what people really think about this.
> >>
> >>
> >>Please write only Yes/No to avoid discussion.
> >
> >
> >
> > readings of my question, which is imprecision on my part.
> >
> > We usually consider equivalence in computability to be a sufficient
> > condition for being a physical example to a model of computation,
> > essentially covering the capabilities of "causal mechanism" involved.
>
> works with, as long as it remains finite. *EVERY* PC has a limit on the
> data it can process. The abstract notion of a PC is equivalent to a TM,
> but we have no abstract PCs, just the real deal with their limitations.
>
> The issue is simple: a PC cannot handle *all* the data a TM can process.
Will, what makes you think that the input tape has to be mapped to
spatial dimensions?
Thanks,
--
Eray
HERC777
>And a brain have not tapes
actually i thought this was poetry. the exact distinction of theory.
but all it means is T.M.s exist in minds AND T.M.s cannot be
practically achieved in minds... there is no implication that T.M.s
have some physical domain from this.
what's pointworthy is a computer can represent 8^100,000,000,000 (100
GB memory) states. DIFFERENT STATES, it can only represent one state
at a time. to model a TM, it requires proportional memory to the
number of states, each state has 2 pointers of 32 bits, so a computer
can only emulate 25 GIGA states. (#1 4 bytes per state).
Is that large? is our memory already seemingly infinite? no.
a computer is a Finite State Machine that emulates a subset of Turing
Machines with
A/ restriction of number of states
B/ restriction on new memory allocations
There are algorithms that would quickly go through terrabytes of
memory. They won't run on PC's.
Herc
#1 Yes I do claim the term Gigastate and all subsiduary rights.
Edward G. Nilges
You are speaking about practical realization and not equivalence.
A PC considered as a system including its owner can always force the
owner to drive to CDW and buy more memory. And, we can deal with the
issue of the owner's mortality by assuming that he tells his children
to keep the TM simulator task running seamlessly, and tell their own
children.
Stranger things have happened, for example in the burial of nuclear
fuel. Chernobyl's data systems today will have to execute
indefinitely.
Indeed, Turing may have been thinking not about a mechanism, but of
the essence of a hardworking Wren (British Army female) clerk at
Bletchley or in civilian life at a mutual assurance society, the sort
of person who year in and year out obeys instructions and is in a
finite number of states.
A Marxist would consider that the proletariat as a whole simulate a
Turing Machine and would identify revolution with the halt state.
The point is that the question of whether a TM can be simulated by a
PC is known and there's no point in a silly poll.
Stephen Harris
"Edward G. Nilges" <spino...@yahoo.com> wrote in message
news:f5dda427.04120...@posting.google.com...
The habit of estimating things as worthless (such as ecological diversity)
is potentially perilous because it often goes hand-in-hand with what the
eminent philosopher Alfred North Whitehead termed the Fallacy of Misplaced
Concreteness. This fallacy involves thinking something is a 'concrete'
reality when in fact it is merely a belief, opinion or concept about the way
things are. And a false belief in something is a delusion - and delusions
can be dangerous.
Process philosophy influenced Germans like Heidigger and Marx
which is quite opposite to neoplatonism.
http://mally.stanford.edu/ "physically possible objects and events":TM tape?
"Welcome to the web pages of the Metaphysics Research Lab. Whereas physics
is the attempt to discover the laws that govern fundamental concrete
objects, metaphysics is the attempt to discover the laws that systematize
the fundamental abstract objects presupposed by physical science, such as
natural numbers, real numbers, functions, sets and properties, physically
possible objects and events, to name just a few. The goal of metaphysics,
therefore, is to develop a formal ontology, i.e., a formally precise
systematization of these abstract objects. Such a theory will be compatible
with the world view of natural science if the abstract objects postulated by
the theory are conceived as patterns of the natural world.
In our research lab, we have developed such a theory: the axiomatic theory
of abstract objects and relations. In many ways, this theory is like a
machine for detecting abstract objects (hence the name 'research lab'), for
among the recursively enumerable theorems, there are statements which assert
the existence of the abstract objects mentioned above. Moreover, the
properties of these abstracta can be formally derived as consequences of the
axioms."
Steven
> Are PCs physical examples to Turing Machines? [*]
mathematical construct devised to analyze the computing capability of a
"computer", which was a job description by the time Turing "invented"
the TM, can hardly be matched by a physical system, which has to
suffer from limited ressources as well as arbitrary behaviour (e.g., it
will eventually terminate due to "external influence", but this does
not solve the halting problem).
The question whether a PC can emulate a TM is rather boring, as the
answer will have to be "no" - but, as I understand it, the unlimited
tape of a TM is not the ingenious part of the definition, but rather
the lack of interest in struggeling with space bounds all the time.
The other direction (can a TM simulate a PC) is more interesting; I am
not entirely sure here. The question is whether the arbitrary behaviour
of a PC due to user input, mechanical breakdowns, heat deaths of the
universe and so on can be simulated by a TM. I think of a "real world"
PC as a hybrid system with an uncountably large state space, and if I
am not mistaken, a TM can only simulate countably many states? Any
opinions?
Thanks, S.
Will Twentyman
Who said anything to do with spatial dimensions? I'm just talking about
how many digits of input a particular machine can accept.
--
Will Twentyman
email: wtwentyman at copper dot net
Stephen Harris
"Will Twentyman" <wtwen...@read.my.sig> wrote in message
Eray has been told dozens of times that TMs are abstract ideas that have
no physical existence. No part of the TM has a spatio-temporal dimension.
The tape is a theorettical/fictional device which has nothing to do with
fitting
inside the boundaries of a physical universe because it is not physical.
The PC is physical and thus has spatio-temporal dimension. The PC requires
a real physical substance for memory. This substance has a similar function
to the tape of a TM; output of a computation can be stored.
There is a limited amount (finite) of physical substance which is called
"matter"
in the physical universe. If all the matter in the universe were used for
memory
storage, every particle in the universe stored one digit of Pi, then Pi
could be
computed to zillions and zillions of places and written to memory.
But at some point in this physical process (PC), all the matter in the
universe
is exhausted (the universe expanding does not create new matter) and more
digits of Pi cannot be written to physical memory.
But because a TM is an abstract (non-physical) device with a tape that
doesn't run out of memory/tape to write digits of Pi, it can store more
digits of Pi than any physical device (PC). Whatever the finite max of
digits that can be stored in PC memory, a TM can store twice as many,
and still be storing a finite number of digits. The TM can store more
digits because it is not physical, it has no physical memory constraints
imposed upon it by the universe; unlike the PC which is physical and
thus does have physical constraints imposed upon it by the universe.
It is a complete mistake to think that Turing defined a TM as a physical
device that could exist within physical reality. Turing described an
abstract,
non-physical, theoretical device. TMs _encode_ some properties that can
be physically actualized in a real computer. TMs do not _exemplify_ PCs.
A TM is not a physical example of a PC, a PC is not a physical example
of a TM. Because by definition, TMs are not physical and PCs are not
abstract, but physical. This is a fact of definition. Because some people
do not understand the definition and others have never even read the
definition does not change this fact. That is why people are saying there
is no such question as are all pcs turing machines?
There are 3 feet in a yard. No more no less. A yard is not a meter.
That is a definitional fact. People might ask if there are 36 inches in a
yard
if they are uneducated. They cannot change the reality of the defintion
because they harbor a delusion that a yard has 39.37 inches. All they
can do is display their ignorance or confusion regarding the definitions
of a yard and a meter. I am making an analogy between a yard and a meter
and a PC and a TM. They have different definitions. A TM is a non-physical
device and a PC is a physical device; they have different definitions.
Stephen Harris
"Steven" <steve...@despammed.com> wrote in message
news:1102324161.5...@f14g2000cwb.googlegroups.com...
>The question is whether the arbitrary behaviour
> of a PC due to user input, mechanical breakdowns, heat deaths of the
> universe and so on can be simulated by a TM. I think of a "real world"
> PC as a hybrid system with an uncountably large state space, and if I
> am not mistaken, a TM can only simulate countably many states? Any
> opinions?
>
> Thanks, S.
>
As I understand it, uncountable always means infinitely uncountable,
whereas countable, can either be finitely or infinitely countable.
The set of all Turing machines is countable. Thus there exists real
numbers that can not be accepted by any Turing machine.
"A Turing machine is a kind of state machine. At any time the machine is in
any one of a finite number of states. Instructions for a Turing machine
consist
in specified conditions under which the machine will transition between one
state and another." The formal definition of a finite state machine is that
it has
a countable number of (thus discrete) states.
I think because there are real numbers that a digital computer does not
accept (but truncates) that a digital computer also has a countable number
of states. Maybe this isn't the best reason, a continuous vs. discrete
criteria,
and will be expounded upon by other posters.
Regards,
Stephen
Stephen Harris
"Steven" <steve...@despammed.com> wrote in message
news:1102324161.5...@f14g2000cwb.googlegroups.com...
There are random influences on PCs, such as cosmic rays. From Google:
> It seems state can also have infinite possibilities. Take computer
> programs. They are state dependent, requiring input before any output is
> given. However, the input seems infinite, which makes determining all
> possible output a virtually impossible task. Hence the software bug.
"OK, this is an interesting point. You are of course right in saying
that there is an infinite range of possible input sequences to
any state machine, because you can leave it running for an infinite
time if you wish and at each time quantum (clock cycle, if you like)
the input can take one of some set of values. So the number
of possible input sequences rapidly blows up, and is limitless
if the machine goes on working for ever.
State machines try to resolve this difficulty by making sure that
the *machine itself* has a well-defined countable number of
possible internal states. At any given moment its state will
depend on its immediately previous state and the *present* value
of its inputs - so, no infinite range of possibilities.
Also, at any given moment its outputs will depend on its present
state and (possibly) its inputs. The rules that the FSM uses to
decide its outputs and its next state from its present state
and its inputs are fixed: they are the design or program of the
state machine.
Keeping the description general like this for a moment, you can
easily see that if the machine has N binary memory cells
inside it, then it must have 2^N possible internal states
representing all possible combinations of those N bits.
(Not all those states may be useful, of course).
A typical PC, ** not counting the disk**, has something like
300 million memory cells in it, most of which are in its RAM.
This humungus "state machine" therefore has 2^300000000 states.
Since there are roughly 2^320 fundamental particles in the
known universe, it's pretty clear that describing the
computer as an FSM is not a going concern. OTOH there are
some important theoretical results that can be obtained
by doing exactly that!"
spino...@yahoo.com
Doesn't have to hold complete numbers: think "events". Is sent digits
just in time. Emits significant digits of product and revises them when
carry forward occurs.
Needs a lot of time but if it starts with most significant digits its
interim answers will be usable approximations. But time can almost
always be traded for space in computation if not in physics. I think
Rudolf Carnap used to go about the University of California campus in
1962, singing softly to himself, to the tune of Gene Chandler's Duke of
Earl:
Raum, raum, raum, raum undt zeit zeit Zeit
Life is short: art is long.
But even if you want to have and to "hold" a 10e4 number, think
biocomputation and the coming ability to inscribe data on molecules, on
cells thereby oops creating designer diseases.
Circa 2020, absent my Social Security (ended by President For Life
Pierce Bush II after the United States Marine Corps was called in 2019
to put down riots in major cities), I might get a job from the NSA as a
human memory chip upon whose T cells is inscribed the expansion of Pi,
in the sky.
I've mentioned in this thread how Ehud Shapiro has found an application
for Turing machines as literally cellular "doctors" operating inside
you to hopefully do no harm yikes.
I mean, it is possible. Desirable? Well, despite all the computation
you could just dance to the rock and roll station. Oh, guess not. Clear
Channel bought it and turned it to all hate talk all the time.
"Porgy Tirebiter, he's a spy and a girl delighter"
"Porgy Tirebiter, just a student like you"
"Just a student like you"
[Stop singing and do your homework]
"Just a student like you-hoo"
>
> --Mark
spino...@yahoo.com
John Schoenfeld
The question relates to physical turing machines.
Mark Nudelman
> Mark Nudelman wrote:
>> I didn't say that a PC couldn't handle an input of X=10^1000. I
>> said that it couldn't perform a calculation that requires 10^1000
>> _storage cells_. (For example, multiplying two numbers, each of
>> which has 10^1000 digits.) There isn't enough matter in the universe
>> to even begin to build a computer that could hold a 10^1000 digit
>> number.
>
> Doesn't have to hold complete numbers: think "events". Is sent digits
> just in time. Emits significant digits of product and revises them
> when carry forward occurs.
You're trying to enhance the PC by adding some kind of input / output device
to hold unprocessed input and temporary results. I would consider that
equivalent to just making the PC's memory bigger. But where in the universe
are you going to hold the input before you give it to the TM, and where will
you store the intermediate results? The problem is NOT that a PC is not big
enough to hold a 10^1000 digit number -- the problem is that the universe
isn't big enough. Moving the storage outside the PC doesn't solve the
problem.
> But even if you want to have and to "hold" a 10e4 number, think
> biocomputation and the coming ability to inscribe data on molecules,
> on cells thereby oops creating designer diseases.
I deliberately chose the example to invalidate this kind of solution. Even
if you inscribed your data on elementary particles, and even if there's a
lot more matter in the universe than we think -- even if the observable
universe was packed solid with electron-sized memory cells, there still
wouldn't be nearly enough memory to hold a 10^1000 digit number (by which I
mean an integer containing 10^1000 digits -- I'm not sure what you mean by
"a 10e4 number").
--Mark
Will Twentyman
There are no physical Turing Machines.
Mitch Harris
>
> There are no physical Turing Machines.
That just seems to be a common way of sidestepping the issue. The
only explanation I can see of your statement is that TMs are
considered to be only theoretical constructs. But that seems to me to
be similar to saying, there are no physical examples of the number 2,
because, of course, 2 is an abstraction. When you have two apples,
you don't have literally the number 2. But everything you want to say
about the number of those apples is in the 2.
--
Mitch Harris
(remove q to reply)
|-|erc
Right. There's no number 2 either, but we can encapsulate the number 2
in physical form, we can't even do that with Turing Machines, they didn't
build the universe big enough.
There's no infinity or circles either! And the cartesian plane... 3 dimensional
immitations, no e, no cos function, no functions at all, not even a zero!! Luckily
there's no 1/x either.
Where do they all come from? maybe plato knows.
Herc
Mitch Harris
> "Mitch Harris" <har...@tcs.inf.tu-dresden.de> wrote in
>>Will Twentyman wrote:
>>
>>>There are no physical Turing Machines.
>>
>>That just seems to be a common way of sidestepping the issue. The
>>only explanation I can see of your statement is that TMs are
>>considered to be only theoretical constructs. But that seems to me to
>>be similar to saying, there are no physical examples of the number 2,
>>because, of course, 2 is an abstraction. When you have two apples,
>>you don't have literally the number 2. But everything you want to say
>>about the number of those apples is in the 2.
>
> Right. There's no number 2 either, but we can encapsulate the number 2
> in physical form, we can't even do that with Turing Machines, they didn't
> build the universe big enough.
I'm not sure that the finiteness or infiniteness of the universe has
been decided empirically, or even if it can be. What experimental
evidence would allow one to know?
|-|erc
even so, entropy will destroy the machine long before it computes BB(20)
Herc
Stephen Harris
"Mitch Harris" <har...@tcs.inf.tu-dresden.de> wrote in message
news:31nubiF...@news.dfncis.de...
> Will Twentyman wrote:
> >
>> There are no physical Turing Machines.
>
> That just seems to be a common way of sidestepping the issue. The
> only explanation I can see of your statement is that TMs are
> considered to be only theoretical constructs.
Yes, that is exactly right. And the people who don't know this
are the people who have only a vague notion of what a TM is.
You can find 50+ definitions on the web which say a TM is an
abstract, or theoretical, or hypothetical, or notional device.
That is the definition which I don't think you learned. There are
only philosophical issues for those who don't know the definition.
>But that seems to me to
> be similar to saying, there are no physical examples of the number 2,
> because, of course, 2 is an abstraction. When you have two apples,
> you don't have literally the number 2. But everything you want to say
> about the number of those apples is in the 2.
>
Not similar to me. You can link twoness to reality. You can point and
say there are two PCs but never point and say there is one Turing tape.
TM tapes are often described as potentially infinite. Infinity is not a
number.
The memory of the TM is boundless. The memory of a PC cannot
be boundless so it does not physically exemplify a TM nor can it
ever without postulating infinite physical parallel universes which
the Many Worlds interpretation does not do.
Where does the physical energy to operate the TM come from?
Nor is there any time constraint on how long a TM computes or
how fast as given in Turing's 1936 paper. These are not properties
which are part of physical reality.
A TM can be partially simulated by a PC. Except for the boundless
memory and the lack of a physically imposed time constraint. But
this is exactly why a TM can compute more finite digits of Pi than
any physical computer, even if it (PC) uses all the matter in the universe
for its memory. And that is the issue this thread is about. Not that PCs
are similar in many respects to TMs, nor denying that PCs drew some of
their inspiration from TMs. Though PCs are closer to von Neumann machines.
David Bernier
Right, say cosmic rays, etc.
Even in a system with a very isolated and protected PC,
if Quantum Theory is correct, the PC and its
surroundings are described by a wave function, so
I guess certainty in the outcome of a computation is
an illusion (?).
David Bernier
Will Twentyman
2 is an abstraction, yes. But it is a well understood abstraction. TMs
are an abstraction as well. Part of the definition of a TM is that it
has an *infinite* tape which functions much like the memory of a
computer. Regardless of how you feel about models, I have never seen,
nor do I expect to see, any device with an infinite dimension.
If you wish to disagree about the possibility of such a device, so be
it. However, I'm not holding my breath.
lui...@yahoo.com
> > >> "Mark Nudelman" <ma...@greenwoodsoftware.com> wrote in message
> > >> news:<BCKrd.600129$mD.87873@attbi_s02>...
> > >>> Eray Ozkural exa wrote:
> >
> > >>> A TM can perform a calculation that requires 10^1000 storage
cells,
> > >>> but no PC or any other physical computer could do that.
> > >
what
> > > a TM is.
> > > The TM dont'n "perform calculations", is the mathematician who
> > > decides what a TM will do if it receives the input X = 10^10000,
and
> > > this can be easily simulated by a PC that can handle powers and
> > > logarithms.
> >
said that
> > it couldn't perform a calculation that requires 10^1000 _storage
cells_.
> > (For example, multiplying two numbers, each of which has 10^1000
digits.)
> > There isn't enough matter in the universe to even begin to build a
computer
> > that could hold a 10^1000 digit number.
> >
>
> When a conceptual machine has calculated two numbers of 10^1000
> digits or handled a matrix of 10^500 x 10^500 ?
> Ludovicus
The Turing Machine and the Eratosthenes Sieve are algorithms for make
predictions about the behavior of certain strings of numbers. But to
say that a Turing Machine can write the product of two numbes with
10^1000 digits, is the same as to say that a Eratosthenes Sieve can
write the 10^1000th prime number.
Ludovicus
ele...@yahoo.gr
Mike wrote:
> "oðin" <oði...@ragnarok.com> wrote in message
news:<MY6dndLAFKZ...@whidbeytel.com>...
> > > Are PCs physical examples to Turing Machines? [*]
> > >
> > > Please write only Yes/No to avoid discussion.
> >
>
> Yes
I confirm: YES (PCs are physical examples [of] Turing Machines.
I explain: I take physical[x] to be an operator, which amongst other
things imposes limitations on its operand, such a tape size
limitations. A theoretical PC with an infinite memory IS a Turing
machine:
Theoretical PC = Turing machine (1)
I apply my operator physical[x] to (1)
physical[theoretical PC] = physical[Turning Machine] (2)
I can do that, Can't I? It's just an operation. From 2:
PC = physical[Turing Machine]
No questions asked:)
Mike
|-|erc
aka the noise demon.
10^(-200) -- This is the probability that an electron in a 1s orbital
of a hydrogen atom is 5 nanometers from the nucleus.
10^(-42,000) -- This is the probability of a monkey typing Hamlet
by chance. [27,000 letters and spaces using 35 keys
implies a one out of 35^(27,000) chance.]
10^(-10^8) -- This is the probability of flipping a coin once a
second for 100 years and getting all heads.
10^(-5.2 x 10^18) -- Using non-relativistic quantum mechanics,
this is the probability that an electron in
a 1s orbital of a hydrogen atom is 240,000
miles from the nucleus (distance to the Moon).
10^(-3 x 10^26) -- Gamow observes (see Chapter 8.4 of [43]) there
is a nonzero probability that all of the air
molecules in a room will collect together
simultaneously on one side of the room, namely
(1/2)^n where n = 10^27 is the number of air
molecules in the room.
10^(-10^93) -- Using non-relativistic quantum mechanics, the
probability that every electron in all the
hydrogen atoms in the sun are 10 billion light
years away is more than this.
10^(10^100) -- One googolplex.
googolplex + 1 -- This number is NOT prime. One of its factors is
316,912,650,057,057,350,374,175,801,344,000,001.
See Crandall [25].
The sun's electrons simultaneously passing Andromeda might cause a glitch!
Herc
Stephen Harris
<lui...@yahoo.com> wrote in message
news:1102519505....@f14g2000cwb.googlegroups.com...
That is correct, I think, if you mean that a Turing Machine could act
as an Eratosthenes Sieve and compute the 10^1000th prime number.
Or the 10^1000000000000000000000000000th prime number.
Anything finitely specified. That is because a Turing Machine is abstract.
That means it is not physical. It is not constrained by time or memory.
Whereas a PC is physical and obeys laws of causality and is
constrained by time and memory.
Turing described a tape that is an imaginary concept.
It never was physical. It never is physical and it can never be physical.
This question in the Subject: is senseless. It is like answering the
question "Are any prime numbers even?" The answer is yes
because of "2" which fits the definition of a prime number.
The defintion of a TM has a tape. The tape is not real, it is a fantasy,
and it can do magical things. There is no such tape in the real world.
There is a saying: if wishes were horses, then beggars would ride.
That means because a human can imagine the concept of a horse
doesn't mean that a person can ride an abstract concept. This analogy
is not exact because there is no such thing as a turing tape contained
in reality. People in science fiction have come up with an abstract
device called a time machine in which they time travel. That does not
mean anybody can actually, in physical reality, build a time machine
or time travel.
A Turing Machine with a tape like Turing describes is purely
a theoretical device. It is not real and cannot be real by definition.
If you know the definition then there is no sense to the Subject question.
It is like not knowing the definition of a prime number; then you might
not know whether there was an even prime number, then it would
seem like a plausible question rather than an admisssion of ignorance
due to poor education.
lui...@yahoo.com
Will Twentyman wrote:news:<320e992a.0412...@posting.google.com>...
>> The issue is simple: a PC cannot handle *all* the data a TM can
process.
The issue is more simple: Turing Machines does'nt exists, only
Turing's algorithms.
Same: Eratosthenes Machines does'nt exists, only Eratosthenes Sieves.
Tell me, which actual TM process has been realized that a computer
could not manage?
Stephen Harris
"Mitch Harris" <har...@tcs.inf.tu-dresden.de> wrote in message
news:31oaq3F...@news.dfncis.de...
There is a great deal of empirical evidence that no new matter
is created in the universe. That does not depend on whether
the universe expands forever, and thus the matter becomes
less dense, but it still the same amount, or whether the universe
contracts, and becomes more dense with matter. There is exactly
the same amount of matter in either situation (e=mc2).
The turing tape is analogous to physically substanced memory.
If all the (fixed amount) of matter in the universe were converted
to physical memory for a PC, it would still only store a finite
number of digits say of the expansion of Pi. If every sub-atomic
particle in the entire universe stored one digit of Pi, eventually
you run out of particles with plenty of Pi digits left to be stored.
A Turing tape never runs out of storage space. It is not physical.
There is no such question as to how much space it takes up because
space is a physical universe concept. The turing tape is imaginary.
A Turing tape can store 10^10000000000000000000000000000000
and more digits than any physical PC when computing Pi or any
other infinite expansion such as the square root of a prime number.
The estimate I saw on how many particles there are in the physical
universe is something like like 10^230 and that limits the calculation
that a PC can do because PCs require physical storage. Even if the
estimate is off, and its 10^230000000000000000 particles available
for physical storage of a computed digit using a PC, is will always
be vastly insignificant in comparison to the magically bestowed potential
of a TM. And the TM tape does not compute in the physical universe,
so the question about whether the tape would fit in the physical universe
depending on whether the universe is finite or expands infinitely is
irrelevant.
Stephen Harris
<lui...@yahoo.com> wrote in message
news:1102540245....@z14g2000cwz.googlegroups.com...
"realized" means physically manifested. So the answer is none of course.
PCs are physical and "realized". Not taking into account time, a PC
could compute max 10^2300 digits of Pi.
TMs are not physical and could compute 10^2300000000000 digits
of Pi and then more than that.
That is quite a difference because a TM is a theoretical device
and a PC is a physical device. This is the point to the question:
Re: Poll: Are PCs Turing Machines?
The answer is NO.
Because the computation of a TM is a theoretical potential which
can never be "realized" by a physical PC. TMs never realize
any potential because there is no such thing as the turing tape
in physical reality. A PC can simulate a TM on calculations that
don't exceed the physical memory capacity of the PC.
That does not make them the same thing because they do not
have the same potential. You can make a physical like TM except
it does not have the turing described tape. So this physical like TM has
physical memory like a PC. It does not have the crucial component
that motivates the whole distinction between TMs and PCs:
A non-physical wonder tape that magically surpasses physical limitations.
Turing imagined this tape. It has never been "realized". TMs don't
do physically realized computations. None at all. PCs do, and that
is why PCs are not Turing machines.
peter_douglass
> Will Twentyman wrote:
disagree.
There exists both the mathematical abstraction "2" as well as
concrete, physical instances of "2" things.
However, there exists a mathematical abstraction of the
Klein bottle, yet there are no known concrete physical
instances of a Klein bottle.
If it were sound to argue that there must be concrete
physical examples of TM "models" given that there
is a TM theoretical abstraction, then it would be
sound to argue the same for Klein bottles.
Since the arguement for Klein bottles is definitely *not*
sound, the argument for TMs is also unsound.
That the theoretical construct "2" has real physical
"models", is irrelevent to whether there are
real physical "models" of TMs.
--PeterD
Mitch Harris
Holding your breath to see if I disagree?
I believe the current science that says that there is a finite amount
of matter.
Even if there were an infinite amount of matter, I also would not
expect to see a device using an infinite amount.
Even if there were such a device, I -know- that I couldn't get an
answer from it that takes an infinite # of steps (whether the device
needs to use all of its physical extent or not).
But none of my objections above were meant to lead in this
direction. I think my objection is to how the distinction between
"theoretical" and "physical" is used. Why isn't the concept "PC" a
theoretical one? Why isn't the subject line "Poll: Are physical
instantiations of Turing Machines also Turing Machines?"
|-|erc
> direction. I think my objection is to how the distinction between
> "theoretical" and "physical" is used. Why isn't the concept "PC" a
> theoretical one? Why isn't the subject line "Poll: Are physical
> instantiations of Turing Machines also Turing Machines?"
>
It's ambiguous. Actually the answer to the original poll is yes. A Turing Machine is
a program, and every PC is shipped with Win-yy, (Linux is a workstation!)
Every PC is equivalent to the Turing Machine that is equivalent to Windows OS.
Of course, when we say Turing Machine we like to refer to the idea of all possible
Turing Machines, but a_ particular Turing Machine is just one program. Space Invaders
is a Turing Machine, Greatest Common Divisor is a turing machine, Windows is
a turing machine, hence PC's are the windows turing machine. If you install more
software, the PC becomes the turing machine that is the composite algorithm
of Windows and that software.
Define TM as algorithm+actuation_device.
Is a PC an algorithm with some actuation device to run that algorithm? YES!
Herc
--
3 years without a joint, a screw, a drink, a coffee, a smoke, a steak, a roast,
a visit, going out, buying other than food, a quiet moment, a drive, a workout, a run..
being your Truman is so much fun
Mitch Harris
>
>>>There are no physical Turing Machines.
>
>>That just seems to be a common way of sidestepping the issue. The
>>only explanation I can see of your statement is that TMs are
>>considered to be only theoretical constructs. But that seems to me to
>>be similar to saying, there are no physical examples of the number 2,
>>because, of course, 2 is an abstraction. When you have two apples,
>>you don't have literally the number 2. But everything you want to say
>>about the number of those apples is in the 2.
>
> disagree.
>
> There exists both the mathematical abstraction "2" as well as
> concrete, physical instances of "2" things.
> However, there exists a mathematical abstraction of the
> Klein bottle, yet there are no known concrete physical
> instances of a Klein bottle.
s/Klein bottle/-1
(I think the negation is easier to manage philosophically)
> If it were sound to argue that there must be concrete
> physical examples of TM "models" given that there
> is a TM theoretical abstraction, then it would be
> sound to argue the same for Klein bottles.
I don't see how soundness of realizability of one concept would be
sufficient for the realilzability of another. I also don't see how
"must" is involved in anything anybody is saying here.
> Since the arguement for Klein bottles is definitely *not*
> sound, the argument for TMs is also unsound.
Right. Again, that's not my argument.
> That the theoretical construct "2" has real physical
> "models", is irrelevent to whether there are
> real physical "models" of TMs.
Hmm...but I do think the analogy is a relevant one. Does a theoretical
circle have a real physical model? If yes, is it an exact model? Where
it is not an exact model, is it at least usefully close?
I think the intent of the OP is to get people to realize that there
is a difference between potential and actual infinity. My point
(obscure as it may be) is that it doesn't matter if there is a
difference, the TM concept works pretty well.
Kent Paul Dolan
> A Turing Machine is a program
No, it isn't, nor is your usual idiocy and megalomania
welcome in comp.theory. We've been through this before,
Herc.
http://groups-beta.google.com/group/comp.theory/msg/cde3d14dc2860120?dmode=source
http://groups-beta.google.com/group/comp.theory/msg/4031e01457e5a372?dmode=source
Now go crawl back in your hole like a nice little troll,
and let the good people converse without your inane and
insane interruptions.
HTH
xanthian.
--
Posted via Mailgate.ORG Server - http://www.Mailgate.ORG
|-|erc
> "|-|erc" <h@r.c> wrote:
>
> > A Turing Machine is a program
>
> No, it isn't, nor is your usual idiocy and megalomania
> welcome in comp.theory. We've been through this before,
> Herc.
right, that's the only literal part that could be misquoted. the result that
the vote is YES relies on the fact a TM is a model of a particular computer.
Actually that's how TM's are defined, there is no parser that runs it, it just works,
however you *could* equally define TM's as programs if you introduced the notion
of some evaluation device.
either way you are wrong and the vote showed it up.
>
>
> http://groups-beta.google.com/group/comp.theory/msg/cde3d14dc2860120?dmode=source
>
> http://groups-beta.google.com/group/comp.theory/msg/4031e01457e5a372?dmode=source
give me the gist of it, I can't be bothered wondering why some random quote you selected
is relevant here hence its fruitless to examine anything you point out.
>
> Now go crawl back in your hole like a nice little troll,
> and let the good people converse without your inane and
> insane interruptions.
>
you're the insane one remember, remember all the decades they've pumped
you with anti-psychotics, because you come across to simple art student
psychologists as a jerk?
Will Twentyman
> "Mitch Harris" <har...@tcs.inf.tu-dresden.de> wrote in >
>
>>But none of my objections above were meant to lead in this
>>direction. I think my objection is to how the distinction between
>>"theoretical" and "physical" is used. Why isn't the concept "PC" a
>>theoretical one? Why isn't the subject line "Poll: Are physical
>>instantiations of Turing Machines also Turing Machines?"
>
> It's ambiguous. Actually the answer to the original poll is yes. A Turing Machine is
> a program, and every PC is shipped with Win-yy, (Linux is a workstation!)
It would be more precise to say a TM is equivalent to a program in a
suitably powerful language. However, it is still necessary to find a PC
that can accept arbitrarily large input. Also, you can buy PCs from
Walmart.com with Linspire as the OS (at least last I checked, when it
was Lindows).
> Every PC is equivalent to the Turing Machine that is equivalent to Windows OS.
Windows OS, however, has no memory.
> Of course, when we say Turing Machine we like to refer to the idea of all possible
> Turing Machines, but a_ particular Turing Machine is just one program. Space Invaders
> is a Turing Machine, Greatest Common Divisor is a turing machine, Windows is
> a turing machine, hence PC's are the windows turing machine. If you install more
> software, the PC becomes the turing machine that is the composite algorithm
> of Windows and that software.
>
> Define TM as algorithm+actuation_device.
>
> Is a PC an algorithm with some actuation device to run that algorithm? YES!
With a few minor differences, like a TM will not exhaust the heap (in
C/C++).
|-|erc
>
> Is a PC an algorithm with some actuation device to run that algorithm? YES!
Examine the more relevant question, is a PC equivalent to a turing machine?
This means, is any given PC equivalent to some turing machine?
How is this possible? Because all the components of a TM have a physical
equivalent except for the infinite tape, but not all TM's require the infinite tape.
Say we construct a TM that uses a finite amount of memory. Its not a trivial machine
that only requires 10 tape cells no matter the input, it has usual complexity requirements
and uses more memory with bigger inputs. (Windows)
STATE COMPONENT
v pointer
|_0_|_0_|_0_|_0_|_0_|_0_|_0_|_0_|_0_|_0_|_0_|_0_|
For the TM to behave like a PC, it must know when it is about to run out of memory.
Here's a solution.
STATE COMPONENT
v pointer
|_1_|_1_|_0_|_0_|_0_|_0_|_0_|_0_|_0_|_0_|_1_|_1_|
Just like monkey flying to the end of the universe on his magic cloud, and writing grafitti
on the 5 pillars to show he had been to the end, on the larger scale of things, he actually
only went to the end of Buddhas arm and painted on her fingers, and decided of his own
accord to return again back into the realms of the possible.
The theoretical concept of infinite memory and a practical model are mutually satisfied.
We can use bitpairs on the tape with the following mapping
00 - 0
01 - 1
10 - ?
11 - EOF
and the TM moves over pair of digits to interpret them.
Now the state component can be set up with all the loaded software of the PC
One complication is interaction. The defn of the TM is that the input is laid out
on the tape before the 1st cycle. The only way a TM could read a keystroke
and respond to it is if this definition is relaxed. Its a bit tricky, especially with
a finite tape and an infinite input stream. The TM would have to point to somewhere
in memory where you can type in some data at that buffer space, scan it, clear it
and then point somewhere else. Functional programs achieve interaction with a
process(keyboard()) function, like so:
keyboard = <abc...>
map(keyboard) = <
<a>
<ab>
<abc>
..
>
process
handle(first(1, map(keyboard())) <a>
hande(first(2, map(keyboard())) <ab>
...
That way it can return a result to the keypress a, but still keep inside the function
and process <ab>, then <abc>. It looks like highly redundant data but the functional
parser handles it cleanly. This is called lazy evaluation, first(3, N) = <1 2 3>
will halt processing (and give a result) even though it has an infinite stream as a parameter.
Not all Turing Machines are PCs.
All PCs are Turing Machines.
Herc
lui...@yahoo.com
Stephen Harris wrote:
> <lui...@yahoo.com> wrote in message
> news:1102540245....@z14g2000cwz.googlegroups.com...
> >
> > Will Twentyman wrote:
> >> Eray Ozkural exa wrote:
> >>
> >> > exama...@gmail.com (Eray Ozkural exa) wrote in message
> > news:<320e992a.0412...@posting.google.com>...
> >>> The issue is simple: a PC cannot handle *all* the data a TM can
> > process.
> >> Will Twentyman
> >
> > The issue is more simple: Turing Machines does'nt exists, only
> > Turing's algorithms.
> > Same: Eratosthenes Machines does'nt exists, only Eratosthenes
Sieves.
> > Tell me, which actual TM process has been realized that a computer
> > could not manage?
> >
>
> TMs are not physical and could compute 10^2300000000000 digits
> of Pi and then more than that.
limitations.
> Turing imagined this tape. It has never been "realized". TMs don't
> do physically realized computations. None at all. PCs do, and that
> is why PCs are not Turing machines.
How a TM could *compute* 10^230000000000 digits of Pi? A computer with
enough time (without tape) *could compute* that chain of digits.
A computer program can also show in the screen the algorithm utilized
by Turing for *trying to compute* that string of digits, and say :"I
analyzed the TM method and I found that it can compute N digits of Pi"
A PC do not only realize numerical calculus, also realize mathematical
demonstrations and develop algorithms. If a mathematician can utilize
the Turing Algorithm a computer also can, and with more confidency.
"There are not worse deafs than that those who don't want to hear"
Jesus
Ludovicus
Stephen Harris
<lui...@yahoo.com> wrote in message
news:1102602451.0...@z14g2000cwz.googlegroups.com...
A TM is an abstract device. Abstract means non-physical. Turing gave
his TM a magical tape that is not physical. The tape is unending and is
not part of the physical universe. Neither is there any time involved. A
TM can compute: Suppose every tree in the world were converted
into sheets of paper. And on the first page you typed 10^2300000
and you went on to fill that page and every other existing page with more
zeros to change 10^2300000 into a power that was zillions and zillions
of zeros larger like 10^2300000000000000000000000000000000
but larger than that, filling all the zillions of pages with zillions and
zillions
of zeros written on them so that the final representation was hugely
staggeringly humongous, hugely larger than a google-googleplex. But
still finite since there are a finite number of trees making a finite number
of sheets of paper making still a finite number of zeros (000...) after the
^.
I am going to call this huge number a metazillion for later reference.
A TM can compute this huge finite number when it comes to computing
finite places of Pi (Pi has an infinite decimal expansion). Because a TM
is not physical, the computation does not occur within the universe.
There is no problem with time or physical storage because those exist
in the physical universe. But not in the imaginary place that the TM with
its imaginary powers does its computation. That is how Turing made up
the TM. It was never physical and can never be physical.
The PC on the other hand is physical. It is limited by the time left in
the universe while there is still energy to power the machine. It is
limited by the amount of matter in the universe. More matter is not
created just because the universe may expand forever. The matter
becomes less dense (it spreads out).
A PC requires matter because it needs a physical substance to store
memory. Every digit of computing Pi needs to be stored onto and
into a physical substance. There is only so much matter in the universe,
so only a finite number of digits (call it Fd) can be stored in the
physical universe if you use every particle in the universe.
The TM is not physical. Not only can it store at one time all the
digits of Pi's expansion that a PC can store (Fd) but much, much,
much, much more. The PC will run out of physical memory even
if it is using all the matter in the universe. All of the digits need
to be stored. One cannot compute some digits and then erase
them and then proceed and compute some more digits and so on.
The computation of Pi on a TM is done on a tape. The tape never
runs out because it is not a physical tape. The tape acts like memory.
Physical memory for a PC, ram, requires physical substance. There
is not enough memory in the physical universe to complete some finite
calculations with a PC. There is always enough time and memory/tape
for a TM to complete its calculation of any finite number no matter
how large, many times larger than a PC, because the TM is not
physical, is not part of the universe, has no time limits set and no
physical limits for memory set.
Turing made up his thought experiment this way. He gave the TM
an unending tape which is not part of the physical universe; the TM
thus has unending memory. It can alway calculate more digits of
some number like Pi because it never runs out of memory, because
it is not physical. The PC will run out of memory because it is physical
and there is going to be a limit to how many digits of Pi it can compute.
Not because of a different algorithm, but because the TM has more
memory given to it by the way Turing invented the TM and its tape.
PCs are not Turing machines because PCs are physical and TMs
are abstract=non-physical. The biggest difference is the TM has
unending memory=tape but the PC always has limited memory
because there is only so much matter to use for physical memory
in the universe. Therefore a PC is going to run out of memory on
some very large calculation that a TM, in principle, can perform.
Shortly, a TM can compute more digits of Pi than the hugest
PC in the universe, or all of them put together, because time is
not a factor for a TM, and memory is never a problem for a TM,
because the TM and its tape are non-physical. No restrictions
that apply to a PC which is part of the physical universe apply to
a TM which is not part of the universe because it is non-physical.
A TM is a mental creation not a real physical machine.
Because that is how Turing imagined and described the TM and
its magically powerful tape. The answer to the Subject:
Re: Poll: Are PCs Turing Machines? is NO, by definition.
There is only a question if one is ignorant of the description/definition.
The question in the Subject would have been better phrased:
Do PCs exemplify Turing Machines? The answer is still NO.
But some of the principles found in the theoretical Turing Machine
are found in the concrete/physical PC. This is sometimes recognized
by saying the TM "encodes" some ideas found in PCs. Also TM
is often used in place of UTM as a generalization.
> A computer program can also show in the screen the algorithm utilized
> by Turing for *trying to compute* that string of digits, and say :"I
> analyzed the TM method and I found that it can compute N digits of Pi"
What does the algorithm have to do with it? The PC can be using a much
more efficient algorithm than the TM to compute Pi, but that is not going to
solve the problem of the PC running out of memory/storage to hold the huge
expansion of Pi's digits, even if the PC uses all the memory in the
universe.
I doubt this (I found that it can compute N digits of Pi) because a TM
can compute N digits of Pi, where N exceeds the memory capacity of
the PC. All those many digits have to be written to physical memory and
there is always going to be an N (that the TM can compute) that is larger
than all the memory of a physical PC can hold or store, no matter how
much memory the PC has, even all the memory in the physical universe.
> A PC do not only realize numerical calculus, also realize mathematical
> demonstrations and develop algorithms. If a mathematician can utilize
> the Turing Algorithm a computer also can, and with more confidency.
There is no such thing as a Turing Algorithm. The PC could use the
same algorithm to compute Pi or a more efficient one to compute Pi.
That is not the problem. The difference is in the memory potential
between a physical PC and a non-physical TM not some algorithm.
A TM theoretically does many of the same functions as a PC. There
is quite a bit of overlap. That is not under dispute. PCs are not TMs
because they cannot do some huge calculations that a TM can perform,
and this is because the physical potential of calculation for a PC is
bounded by the physical restraints of the universe and there are no
physical restraints which limit huge calculations for TMs because they
are not physical. TMs potential for calculation is always greater than PCs.
Because sometimes they can both do the same calculations, doesn't
change the important difference of when they cannot do the same
calculation to same amount of digits. There are finite numbers big enough
that a PC cannot complete the calculation but a TM can complete the
calculation just because the TM has been given more theoretical memory.
> "There are not worse deafs than that those who don't want to hear"
> Jesus
> Ludovicus
>
Take your own advice. PCs are real and TMs are imaginary and
that is why they are not the same but different. For PCs and TMs
to be the same, they have to be the same in all ways, not some
ways or even most ways. TMs are hugely different in a very
important way. They have imaginary tapes that do calucaltions
without taking up any physical time or space; no physical resources.
PCs do not have magical memory nor can they be given unending
memory. The memory for a PC will always come to an end if
the calculation is large enough and there is no way to get around it.
Stephen Harris
<lui...@yahoo.com> wrote in message
news:1102602451.0...@z14g2000cwz.googlegroups.com...
>
> Stephen Harris wrote:
>> <lui...@yahoo.com> wrote in message
>> news:1102540245....@z14g2000cwz.googlegroups.com...
>> >
>> > Will Twentyman wrote:
>> >> Eray Ozkural exa wrote:
>> >>
>> >> > exama...@gmail.com (Eray Ozkural exa) wrote in message
>> > news:<320e992a.0412...@posting.google.com>...
>> >>> The issue is simple: a PC cannot handle *all* the data a TM can
>> > process.
>> >> Will Twentyman
>> >
>> > The issue is more simple: Turing Machines does'nt exists, only
>> > Turing's algorithms.
>> > Same: Eratosthenes Machines does'nt exists, only Eratosthenes
> Sieves.
>> > Tell me, which actual TM process has been realized that a computer
>> > could not manage?
> Ludovicus
>> >
> enough time (without tape) *could compute* that chain of digits.
> A computer program can also show in the screen the algorithm utilized
> by Turing for *trying to compute* that string of digits, and say :"I
> analyzed the TM method and I found that it can compute N digits of Pi"
> A PC do not only realize numerical calculus, also realize mathematical
> demonstrations and develop algorithms. If a mathematician can utilize
> the Turing Algorithm a computer also can, and with more confidency.
> "There are not worse deafs than that those who don't want to hear"
> Jesus
> Ludovicus
>
I may have realized why you brought up algorithms. The input
algorithm for computing Pi for both a TM and a PC is short.
This is not about inputting some huge number.
You have been told before it is about the output. The output
is what requires the huge amount of memory/storage capability.
Every single finite digit of the metazillion output must be stored
in physical memory for a PC, it has to be able to hold all those
digits at the same time. The PC cannot do this with all the matter
in the universe converted to memory for the PCs use.
But the TM has enough memory, it can store every outputted
digit of a metazillion and larger finite numbers, the TM can
hold all those digits at once because it has an imaginary concept,
a potentially unending tape, which is not made of matter because
it is not physical. The tape is like a little magic box that can hold
all the finite objects in the universe because it doesn't store them
in any part of physical existence but in non-physical imagination.
The TM and the tape are this way because that is how Turing made it up.
The TM only exists in reality as an idea, a concept, not as a physical
thing.
You can ride a horse that drinks water, but you can't ride a unicorn which
has a magical horn that purifies contaminated water. TMs and unicorns
exist as concepts in our reality, but not as real physically performing
things.
PCs are real performing things with physical limitations that TMs don't
have,
Stephen
|-|erc
> his TM a magical tape that is not physical. The tape is unending and is
Is a set of traffic lights an automation?
YES
Is there a TM for every algorithm?
YES
Do all algorithms require unlimited memory?
NO
Therefore, a class of physical devices not requiring infinite memory could be TMs.
>
> A TM can compute this huge finite number when it comes to computing
Yes, but the question is about PC's.
>
> The PC on the other hand is physical. It is limited by the time left in
The PC runs through a set of operations in sequence, the outcomes are dependant
upon the state structure that is part of the PC. The TM also runs through a set
of operations in sequence, time is not a factor.
>
> Take your own advice. PCs are real and TMs are imaginary and
> that is why they are not the same but different. For PCs and TMs
> to be the same, they have to be the same in all ways, not some
Are PC's the same as Turing Machines, that is a different question.
Herc