Return Styles: Pseud0ch, Terminal, Valhalla, NES, Geocities, Blue Moon. Entire thread

Computability

Name: nye 2007-11-03 23:54

To start, let me first admit ignorance in the realms of complexity, incompleteness, etc.  I have not yet taken those classes and am still at the popular science level.

Can any computer compute any problem?  If not, what makes a universal Turing machine special in that regard?
On a similar note, could, say, my 1995 Pac Bell computer run modern applications (architectural differences aside) given enough time?  Or are there other constraints in place, such as more RAM needs that could be lifted for the sake of argument to make that computer capable?

This is a purely academic curiosity.

Name: Anonymous 2007-11-04 1:16

The only thing that stops modern computers from being universal Turing machines is the fact that they don't have infinite memory. That is, both your current computer and your "old" Pacard Bell can compute anything that is computable, assuming they have sufficient memory.
Note that there are classes of problems that can't be computed regardless, though. The halting problem is the most famous one.

Name: Anonymous 2007-11-04 1:54

Ah, exactly what I thought.  Thank you.

Name: Anonymous 2007-11-04 9:29

>>1

No. Computers (that are Turing equivalent; ie. all of them) can not compute any problem. For example they can not compute the halting problem. Google that up.

Name: Anonymous 2007-11-04 11:18

Anon, can you write me a program that will tell me if my code has an infinite loop in it?

Name: Anonymous 2007-11-04 12:24

The halting problem is silly.  Yogi Bera said "it ain't over till it's over".

Name: mis4tune 2007-11-04 19:39

modern/non modern computers are capable of solving anything that is explainable/convertable in math numerical methods within a certain amount of time depending on the machines capabilites

Name: Nye 2007-11-04 19:51

>>7
So basically "computers can solve what they can solve."

Prove it!

Name: Anonymous 2007-11-06 2:18

Hey, you mother fuckers are forgetting about HYPERCOMPUTATION.  Halt that.

Name: Anonymous 2007-11-06 6:43

>>9
Undecidability still exists in hypercomputational systems, cockbag.

Newer Posts
Don't change these.
Name: Email:
Entire Thread Thread List