decoration decoration
Stories

GROKLAW
When you want to know more...
decoration
For layout only
Home
Archives
Site Map
Search
About Groklaw
Awards
Legal Research
Timelines
ApplevSamsung
ApplevSamsung p.2
ArchiveExplorer
Autozone
Bilski
Cases
Cast: Lawyers
Comes v. MS
Contracts/Documents
Courts
DRM
Gordon v MS
GPL
Grokdoc
HTML How To
IPI v RH
IV v. Google
Legal Docs
Lodsys
MS Litigations
MSvB&N
News Picks
Novell v. MS
Novell-MS Deal
ODF/OOXML
OOXML Appeals
OraclevGoogle
Patents
ProjectMonterey
Psystar
Quote Database
Red Hat v SCO
Salus Book
SCEA v Hotz
SCO Appeals
SCO Bankruptcy
SCO Financials
SCO Overview
SCO v IBM
SCO v Novell
SCO:Soup2Nuts
SCOsource
Sean Daly
Software Patents
Switch to Linux
Transcripts
Unix Books

Gear

Groklaw Gear

Click here to send an email to the editor of this weblog.


You won't find me on Facebook


Donate

Donate Paypal


No Legal Advice

The information on Groklaw is not intended to constitute legal advice. While Mark is a lawyer and he has asked other lawyers and law students to contribute articles, all of these articles are offered to help educate, not to provide specific legal advice. They are not your lawyers.

Here's Groklaw's comments policy.


What's New

STORIES
No new stories

COMMENTS last 48 hrs
No new comments


Sponsors

Hosting:
hosted by ibiblio

On servers donated to ibiblio by AMD.

Webmaster
Re: Computational complexity... | 135 comments | Create New Account
Comments belong to whoever posts them. Please notify us of inappropriate comments.
Re: Computational complexity...
Authored by: Anonymous on Tuesday, June 11 2013 @ 03:28 AM EDT
"What on earth has this got to do with Groklaw?"

Nothing, that's why it's in OFF TOPIC


A human brain performs some form of calculation. Saying that it doesn't is
denying reality. You don't need more of a model than that to ask the question
of how powerful it is. You may need a more accurate model than that to answer
it.


A non-deterministic Turing Machine is *not* more powerful than a turing machine
in terms of which problems it can solve. It's just trading time complexity for
space complexity by parrallelising. Finitely smaller costs in time is not the
same as being able to solve more problems.

It can be simulated on a deterministic turing machine.

By definition: If you can simulate it on a machine, then it's equivilent or less
powerful than that machine.


And to adress your tangent:
It's perfectly possible to have a finite amount of space, with an infinite
amount of detail. See Fractals.

[ Reply to This | Parent | # ]

Groklaw © Copyright 2003-2013 Pamela Jones.
All trademarks and copyrights on this page are owned by their respective owners.
Comments are owned by the individual posters.

PJ's articles are licensed under a Creative Commons License. ( Details )