Talk:List of open problems in computer science

From Wikipedia, the free encyclopedia

	This article is within the scope of WikiProject Computer science, which aims to create a comprehensive computer science reference for Wikipedia. Visit the project page for more information and to join in on related discussions.
Stub	rated as Stub-Class on the assessment scale
Mid	rated as Mid-importance on the assessment scale

1 Deletion of speedup section
2 Simple one way function?
3 One way functions and the P=NP question
4 Computability
5 Removal
6 Overall
7 Add "definition of algorithm" to the list
8 Church-Turing thesis?
9 Need many more entries
10 Style, categories, qualifications
11 Computer go
12 Artificial Intelligence
13 Quantum Computers and Classical Computers
14 Algorithm: what is such a beast?

[edit] Deletion of speedup section

The original speedup section is posted verbatim in this section below my objections. As stated it appears to confuse the meaning of "speedup" used in the "speedup theorem" (which allows one to achieve a "speedup" by changing the alphabet size -- and potentially causing a combinatorial explosion in the (still finite) number of states in the FSM component of the turing machine) to the notion of "speedup" used by a programmer performing constant-factor optimizations on a fixed-architecture machine.

As stated the problem appears to be fairly close (up to a constant factor) to the problem of finding asymptotic lower bounds to the running time of all correct solutions to a class of problems. The common way to refer to the class of "asymptotic lower bound" problems is to call it "the field of computational complexity thoery." It should be noted that the other (two at the current point!) "open problems in computer science" listed on this page are both from the domain of computational complexity theory, although it would be nice (in addition to having a solution to P vs. NP) to have a general mechanism for finding hard lower bounds on classes of problems, which appears to be what the original "speedup" section was asking for ;).

To what degree can one speed up a computation?

Field: High-performance computing
Description: Although the speedup theorem from computability theory shows that any computation can be sped up by any desired constant degree, there is no feasible method of gaining such a speedup. It is needed to know what are the techniques and bounds on speedup in various architectures - a single processor, grid, distributed network, etc.
Importance: The speed of computation is the limit to the problems that we can solve.
Conjecture: Amdahl's law is a partial answer to the question. —The preceding unsigned comment was added by Mschures (talk • contribs) 05:54, 20 December 2006 (UTC).

[edit] Simple one way function?

Wouldn't A = B * C be a simple one-way function? Any functions which takes two inputs and produces only one output is impossible to reverse unless one of the input parameters are known. - Andrew Price

When people on cryptography say one-way function, it is usually implied that it is possible, although difficult, to invert the function. In fact, if you add the assumption that B and C are prime numbers (so that there is only one solution), the problem you describe is a very likely candidate for a real simple one-way function. It is easy to multiply two large numbers, however it is very difficult to factor a large number into its two primes. There are lots of places to read more on this topic. Meekohi 14:35, 7 August 2006 (UTC)

Just last night I read about the use of the logical OR (inclusive) to destroy any chance of reversability. But I can't remember where I read it. I.e. given a state machine with multiple entries into a state, we cannot retrace how the machine came its current state. But where the hell did I read this? I bet it was Minsky (1967).wvbaileyWvbailey 15:20, 31 August 2006 (UTC)

[edit] One way functions and the P=NP question

Aren't the P vs. NP and the one-way function problems supposed to be one and the same? Somebody, please explain this to me. Brendan 19:47 GMT, 06 Nov 2004

There is a lot of similarity between the problems but they are different. The P/NP question is whether one can compute in polynomial time what it can verify polynomial time. A one way function is a function the is hard to invert though easy to compute. One way functions pose harder problems. Solutions to many NP-complete problem can be approximated while if one way function exists they cannot be approximated. APH 06:45, 7 Nov 2004 (UTC)

Question: If P is not equal to NP, surely this means that one way functions exist -- since an NP problem would be one way? Am I still missing something?

Thanks. Brendan 07:12, 07 Nov 2004 (UTC)

If P=NP then there are no one way functions. If they are different, one-way function still might not exist. In NP-Complete problems, a small number of hard instances are enough for computational hardness. NP-complete problems might have approximate solutions and so. In one-way function we demand that the function will not be invertible, which is a stronger demand.APH 06:24, 23 Dec 2004 (UTC)

As I understand it, the discrete log problem is already in NP, so if P does not equal NP then the OWFs built using discrete log all work. So unless I'm mistaken then the existance of OWFs and the P=NP problem are equivalent. Someone speak up if I'm wrong about discrete-log being confirmed in NP, because I can't find a source for that offhand. Meekohi 05:59, 30 December 2005 (UTC)

The discrete log problem is in NP, and that is trivial to prove. (Proof: the discrete log value is the certificate, verifiable in poly time by modular exponentiation, even the naive algorithm for which is poly-time.) However, I think you're confusing "in NP" with "NP-complete." The discrete log problem is not known to be NP-complete, which is what it would have to be in order for "P not equal to NP" to imply "discrete log creates one-way functions." There are also some theoretical arguments suggesting good reasons to think that discrete log isn't NP-complete; for instance, it is random self-reducible, and if any random self-reducible problem were NP-complete then the polynomial hierarchy would collapse, which would be a surprising result of the same general nature as P=NP though perhaps not quite as surprising as P=NP. Bottom line: P not equal to NP doesn't automatically mean OWFs exist, and even if OWFs exist that doesn't mean discrete log OWFs are legitimate OWFs. Of course, this answer is probably too late to be useful to the original asker of the question. 216.75.183.126 (talk) 03:33, 5 March 2008 (UTC)

See One_way_function#Existance :"It is not known whether one-way functions exist. In fact, their existence would imply P≠NP, resolving the foremost unsolved question of computer science.". Note that though the discrete log is usually used as a one way function but it is not necessarily so. It might be that there are one way function while discrete log is not such. APH 09:28, 1 January 2006 (UTC)

After thinking about it some more I agree with APH. It seems like it is possible for P=NP, and yet there still be one-way functions. P=NP doesn't mean EVERYTHING is polynomial time, there are still problems outside of NP, and these could potentially be used to make a one-way function. Am I understanding that right? Meekohi 18:33, 1 January 2006 (UTC)

It is a bit more delicate. For any time bound, there are functions that cannot be computed within it (like the bounded halting function). However, most such function cannot be used as one way function since one way function should be easy to compute (hence in P).APH 09:10, 2 January 2006 (UTC)

[edit] Computability

I cut this section from the article as it is not an open problem. Since the thesis relates an informal notion ("effective computation") with a formal one it cannot be formalized without removing its contents. So this makes no sense.

Formalize Church-Turing thesis so it can be proved or disproved

Source: See Origins of the thesis

Description: The thesis states that every effective computation or algorithm can be carried out by a Turing machine. Since the term computation is not well defined, the thesis cannot be evaluated.

Importance: The proof of the thesis will show that Turing machine is indeed a universal computation device. Showing that the thesis is wrong will lead to a new kind of problems that are not computable.

Current conjecture: Turing machines were shown to be able to compute in computation possible in many computation models. It is conjectured that the thesis is true.

If you want to restore this section, please give references for experts in the field who consider it an open problem. Gdr 19:34, 2004 Nov 7 (UTC)

Formalize (axiomitize) the Church-Turing thesis so that it can be proved or disproved

Source:

Nachum Dershowitz and Yuri Gurevich 2007, “A Natural axiomization of Church’s Thesis”. It appears on Gurevich’s website at http://research.microsoft.com/~gurevich. Observe not only the title, but the very first lines of the paper -- a quote from Shoenfield:

”We can write down some axioms about computable functions which most people would agree are evidently true. It might be possible to prove Church’s Thesis from such axioms – Joseph Shoenfield (1993)” (Dershowitz and Gurevich, 2007:1)

Dershowitz and Gurevich deliver their thesis in a nutsell:

”Hence, it remains of real importance to provide a small number of convincing postulates in support of Church’s Thesis. Indeed, Gödel has been reported (by Church in a letter to Kleene cited by Davis in [18] [18: Martin Davis, “Why Gödel didn’t have Church’s thesis”, ‘’Information and Control’’, vol. 54, pp. 3-24, July/August 1982] ) to have believed “that it might be possible . . . to state a set of axioms which would embody the generally accepted properties of [effective calculability], and do something on that basis.”

”[Georg] Kriesel described the discovery of “evident axioms about constructive functions” as “one of the really important open problems [40] [40: Georg Kreisel, “Mathematical logic,” in T. L. Sasty, ed., Lectures in Modern Mathematics III, Wiley and Sons, New York, pp. 95-195, 1965 ] and “one of the more feasible problems at the present time” [41] [41: Georg Kreisel, “Mathematical logic: what has it done for the philosophy of mathematics”, in Ralph Schoenman, ed., Bertrand Russell: Philosopher of the Century, Allen & Unwin, London, pp. 201-272, 1967.]

”We propose just such an axiomatization in the sections that follow. We demonstrate that, under certain very natural hypotheses regarding algorithmic activity . . . Church’s Thesis is in fact provable.” (p. 4)

Samual R. Buss, Alexander S. Kechris, Anand Pillay, and Richard A. Shore, June 2000, “The Prospects for Mathematical Logic in the Twenty-first Century”. This paper came from a panel discussion of the Association for Symbolic Logic held in Urbana-Champain. Shore stated the following three problems under the heading “Computer Science” :

”1. “Prove the Church-Turing thesis by finding intuitively obvious or at least clearly acceptable properties of computation that suffice to guarantee that any function so computed is recursive . . .. Perhaps the question is whether we can be sufficiently precise about what we mean by computation without reference to the method of carrying out the computation so as to give a more general or more convincing argument independent of the physical or logical implementation.

”2. What does physics have to say about computability (and provability or logic)? Do physical restrictions on the one hand, or quantum computing on the other, mean that we should modify our understanding of computability or at least study other notions?

”3. Find, and argue conclusively for, a formal definition of algorithm and the appropriate analog of the Church-Turing thesis. . ..Thus we want a definition that will up to some precise equivalence relation capture the notion that two algorithms are the same as opposed to just computing the same function.” (p. 7-8)

Description:

The thesis states that "effective computation" (calculation) or algorithm can be carried out by a Turing machine (or an equivalent abstract computational device), for example, a deterministic, discrete-state, sequential, space-time limited (i.e. "bounded") process/method. But since such notions of “effective computation” are not well-enough defined and not presented as a small collection of axioms (Gödel's proposal), the thesis cannot be proven; rather, as was done by Kleene (who proposed the thesis) it must either be accepted as a conjecture based on "intuition" i.e. heuristics and empirical methods (observation and accumulation of evidence), or perhaps presented as a "definition" (the approach taken by Church and hotly criticized by Post), or else deemed a "natural law" requiring "continual verification" (Post's proposal hotly criticized by Church).

Importance:

Acceptable axioms and a proof of the thesis will show that any behavior that can be called "computational" can be done by a Turing machine or equivalent. To show that the thesis is wrong will demonstrate or lead to new kinds of problems that are not computable and/or new methods that compute what cannot otherwise be computed by a Turing machine (or equivalent).

Current conjecture:

Axiomatization is possible and the thesis is true.

I’ve rewritten the above to more closely represent the question, as I understand it. The following paper, just newly placed on Gurevich’s website, should satisfactorily appease the questioner above, as it quotes from both Paul Schoenfield, Georg Kreisel and Kurt Gödel as well as the authors themselves. Actually, the problem is well known, and I’m surprised someone took issue with it. After the appearance of Turing’s machines, Gödel in particular had not much use for general recursion and lamda-definability as foundations for the notion of “effective computability”; I know of two Gödel-quotes to substantiate this. See much more history at Talk:Church-Turing thesis.

The paper, by Nachum Dershowitz and Yuri Gurevich, is titled “A Natural axiomization of Church’s Thesis”, and it appears on Gurevich’s website at http://research.microsoft.com/~gurevich. Observe not only the title, but the very first lines of the paper -- a quote from Shoenfield:

Dershowitz and Gurevich deliver their thesis in a nutsell:

Clearly from this, an open problem exists, or existed at the time when Godel, Kreisel and Schoenfield didn’t have an answer. Nowadays, Blass (another Gurevich collaborator) Dershowitz, Gurevich, Moschovakis (a dissenter re his article “What is an Algorithm?” (2001) ), myself, and CMummert, (cf long discussion at Talk:Algorithm ) have not seen an adequate axiomitization and proof. So therefore either the problem is presently open, or some folks out there in wikiland know something that Blass, Dershowitz, Gurevich, Moschovakis, CMummert and myself are unaware of.

I would say, given the demonstrated quotations above, that the burden of proof is now on the questioner(s) to show that an axiomization of premises leading to and subsequent proof (or disproof) of Church’s thesis has been successful. wvbaileyWvbailey 15:39, 31 July 2007 (UTC)

Other mathematicians presently involved in this are Robert Soare, and in particular Wilfried Sieg (cf Wilfried Sieg, June 1997, "Step by Recursive Step: Church's Analysis of Effective Calculability", The Bulletin of Symbolic Logic Vol. 3, No. 2, also available on the web). Another important contributor was Robin Gandy. wvbaileyWvbailey 15:18, 2 August 2007 (UTC)

I just found a fantastic article at http://math.ucsd.edu/~sbuss/ResearchWeb/FutureOfLogic/paper.pdf (cited in a 2007 Dershowitz-Gurevich paper):

Samual R. Buss, Alexander S. Kechris, Anand Pillay, and Richard A. Shore, “The Prospects for Mathematical Logic in the Twenty-first Century”.

This paper came from a panel discussion of the Association for Symbolic logic held in Urbana-Champain, June 2000. In particular, under the heading “Computer Science” Shore stated the following three problems for computer science:

There is more from the other authors, including Sam Buss’s question about artificial intelligence, “logic for computer science”, etc. I highly recommend reading this article if someone is interested in expanding this wiki-article. wvbailey

[edit] Removal

I removed the following because a)it's an engineering problem, not a CS problem, and b)it's not a problem at all in non-consumer hardware.

How can one deal with the memory wall?

Source:

Description: In today's computers memory access is becoming very slow when compared to CPU cycles. Hence, the memory access, like hard disk access, might become the term that bounds computation speed.

Importance: This is another important bound on fast computations.

Current conjecture:

a) Well, I actually heard about the problem from a cs researcher doing a post doc on it. I don't think that he will be happy if I'll use his name but I'll see.

The border between cs and engineering is quite unclear. Since you can deal with this problem in a completely theoretic model, I think that it can be considered as cs.

b) I didn't understand your intention in non-consumer hardware. This problem raise when dealing with high performance computing and indeed not in personal computers. So what? The P=NP question doesn't disturbs most computer users too.

I have a feeling that I didn’t understand your reasoning.

Please explain it a bit more.

Thanks, APH 15:56, 24 May 2005 (UTC)

My thought is that the 'memory wall' doesn't qualify as an open problem in terms of this page, because 1) there are already work-around solutions in place and 2) solving this problem would not have a 'major' impact on the field at the level of P=NP or disproving one-way functions (which would break public key cryptography). These requirements are not well spelled out on the main page, but the 'open problems' list seems to be for fundamental problems. --Sgorton 15:34, 13 February 2007 (UTC)

[edit] Overall

This page needs a major rewrite. The problems seem randomly chosen, and there seem to be few factual errors: a) "If one-way functions exist then public key cryptography is possible." This is simply wrong; as far as we know OWFs do not imply public key encryption (they do imply signatures, though). b) "the speedup theorem from computability theory shows that any computation can be sped up by any desired constant degree". This is also wrong. That is not at all what the speedup theorem shows.

Feel free to make edits; one should be bold here. --Mgreenbe 11:18, 30 January 2006 (UTC)

I know i can make edits. But even if I invest the time to fix the errors here, I still would think that this page should rather be deleted. A random collection of some open problems is worth less than no collection at all, in my opinion.

I am sorry, but I do not have the time required to make this a good page.[unsigned, undated]

I think this is a fun and useful page, kind of in the spirit of Hilbert's problems. Read the talk page of Turing machine re the problem of what is and is not "computable" by what, i.e. analog vs digital/logistic computation. The page just needs more input.wvbaileyWvbailey 20:33, 16 August 2006 (UTC)

[edit] Add "definition of algorithm" to the list

One would think that "algorithm" is a perfectly-understood word. I too was surprised. Not so: in the same way the Church-Turing thesis is unresolved we see the need for a definition of what an algorithm really truly is/is not. For example see the work of Blass and Gurevich (2003) Algorithms: A Quest for Absolute Defintions (exact reference to be found at algorithm -- can be gotten off the microsoft website). I will add this after a while if no one objects.wvbaileyWvbailey 20:33, 16 August 2006 (UTC)

[edit] Church-Turing thesis?

Calling this an "open problem" is a bit of a stretch. Calling it a "problem" at all is a stretch. It's not a statement which needs to or can be proved or disproved mathematically. You could say it's a philosophical conundrum, but it's not an open problem in the usual (mathematical) sense. Staecker 00:24, 31 August 2006 (UTC)

All that we need to refute the thesis is a single counter-example. Perhaps the study of "mind" will yield non-algorithmic "methods" i.e. not Church-Turing equivalent but nevertheless effective at calculating more numbers that can be "calculated" by any Turing machine/algorithmic method. My guess is: this remains in the realm of "Hilbert's 20 questions" and continues to drive mathematics foundations. Now whether or not it is driving computer science is another question. I suspect it is: hence, "quantum computation/hypercomputers", etc. I vote it stays on the list: it provokes exactly this sort of interesting (and perhaps useful) dialog.wvbaileyWvbailey 15:12, 31 August 2006 (UTC)

We need a single counter-example, but what exactly would that mean? According to the statement in the article, that would require a process satisfying "an intuitive idea of computation" which cannot be modeled by a Turing machine. But such a statement cannot possibly made mathematically rigorous- using phrases like "intuitive idea" is a dead giveaway for metamathematical content. Since it's not mathematical, I don't think we can call it an "open problem". Perhaps philosophical interest in the thesis drives some research today, but that doesn't make it an open problem. Staecker 16:56, 31 August 2006 (UTC)

Kleene (re his (1952) Introduction to Metamathematics) would disagree that metamathematics isn't a topic for mathematics. But Minsky (1967) seems to agree with you, never mind he's not too convincing with his "intuitive argument" using appeals to "intuitive arguments". In his discussion of "an effective procedure a.k.a. algorithm" (his definition, in fact) he says the matter is subjective:

"Different people may not agree on whether a certain procedure should be called effective. Perhaps there are processes, we might suppose, which simply cannot be described in any formal language, but which can nevertheless be carried out, e.g., by minds. One might even argue that those important, but still mysterious, functions which make minds superior to all presently known mechanical processes must, by their intuitive nature, escape any systematic description.

"Turing discusses some of these issues in his brilliant article, 'Computing Machines and Intelligence' [1950] .. they amount, in my view, to a satisfactory refutation of many such objections." (p. 107)

Minsky goes on to state:

"One cannot expect to prove Turing's [his name for the Church-Turing] thesis, since the term 'naturally' relates rather to human dispositions than to any precisely defined quality of a process. Support must come from intuitive arguments..." (p.108)

Boolos and Jeffrey (1974, 1999) are more constructive:

"Although this thesis ('Church's thesis') is unprovable, it is refutable, if false. For if it is false, there will be some function which is computable in the intuitive sense, but not in our sense. To show that such a function is computable in the intuitive sense, it would be sufficient to give instructions for computing its values for all (arbitrary) arguments, and to see that these instructions are indeed effective....To show that such a function is not computable in our sense, one would have to survey all possible Turing machines and verify (by giving a suitable proof) that none of them compute that function.... Then if Church's thesis is false, it is refutable by finding a counterexample; and the more experience of computation we have without finding a counterexample, the better confirmed the thesis becomes." (italics in original, p. 20)

"Thus, the sun always rises because the sun has always risen." Truth by enumeration: animal logic. Bertrand Russell would have a field-day. At least Boolos and Jeffrey offer us a "road map" of how to go about approaching the problem. But they fall into the same trap: they are asserting that if a computational procedure isn't mechanical then it must be intuitive. Say what? that the world of computation is divided into two mutually-exclusive sets: "the intuitive" and "the mechanical"? Sure sounds like dualism to me ... intuitive 'minds' with 'souls' vs 'brains'made of gooey mechanical stuff ... interesting... most (but not all) philosphers of mind have given up on 'souls' ... maybe here is how one disproves or proves dualism? To wit:

What would be interesting would be if someone could prove that the truth of the Thesis is formally undecidable in any construct whatever, "intuitive or otherwise"-- forever unknowable to man or machine or God. One little [dualism] difficulty: what the hell does 'intuitive' really mean? [maybe that God is punching holes through the 5th dimension into our 4-D space-time, and is seeding minds with "notions" (but not mechanically altering them in the process)?]

I would call this sort of discussion a 'foundations of mathematics' debate, and therefore an open topic in some domain or other. Whether its 'philosophy' or 'foundations of mathematics' I don't know. I think they are the same. wvbaileyWvbailey 19:06, 31 August 2006 (UTC)

[edit] Need many more entries

At one time there were more entries focused on technique and simulation and the practive of computer science. Now the page has devolved into a mathamatical discussion. I would much prefer a list like the unresolved problems in physics list. Ggb667 14:40, 31 August 2006 (UTC)

I agree that the list doesn't seem fully representative of known problems in computer science. I'd recommend the INFOSEC Research Council's Hard Problems list at http://www.infosec-research.org/docs_public/20051130-IRC-HPL-FINAL.pdf for a source of unresolved open problems in the computer security domain. I have to believe there are lists of known problems in other domains, particularly software engineering. --Sgorton 05:12, 5 February 2007 (UTC)

Agreed. It paints a depressing picture of the field that these are the only problems significant enough to make it to this list. If this were truly the case, all computer scientists could pool efforts on P=NP, declare computer science solved, and go find something else to do! I'd add some myself, but the problems I'm currently working on are far more esoteric (and far less important) than the ones listed here. Metasquares 18:44, 29 July 2007 (UTC)

I would like to suggest bold edits. Any problem whose resolution is a publishable result belongs to this page. If the list becomes to long, we merely create relevant subpages and categorize properly. If only so much work is intended, obviously entries that cover more important, well-known, many et.c. problems are more valuable, i.e. it is more valuable to write an article on BPP=NP? than something less popular such as E=AM?, or even better Deciding relationship between Complexity Classes. C. lorenz (talk) 12:55, 26 January 2008 (UTC)

[edit] Style, categories, qualifications

I've placed some of the categories - those relating to specific problems - against the section heading rather than at the end of the article which would be in accord with the WP:MOS. The reason is to make the article easier to maintain. As problems are added and removed the categories will change and if they're not associated with a particular problem then we'll end up with the article being in inappropriate categories. Placing the category entries in the corresponding section is the simplest way to do this. It's not essential, but clean. -- JDX 05:19, 29 September 2006 (UTC)

What qualifies a problem to be included? P=NP is obvious, but the others aren't. Challengelist is the only list I can find. I propose removing the UET and Relay Channel problems, and that problems shouldn't be included unless there's an external source justifying it and a separate article about the problem. -- JDX 05:19, 29 September 2006 (UTC)

These two problems have been removed:

What is an optimal UET scheduling algorithm for 3 processors with precedence constraints?
Capacity of the Relay Channel

The article version with them is: 2006-11-27 The reason is that there's no justification for them as major problems. Perhaps someone familiar with the issues could write articles giving more details on these problems, and then reinstate them. -- JDX 03:26, 27 November 2006 (UTC)

[edit] Computer go

Computer go is absolutely not an open problem in computer science. The reasoning is similar to the Church-Turing thesis above but much stronger. It is trivial to write an O(1) algorithm to play perfect go on a board of a particular size, just as solving chess was a trivial problem, just computationally infeasible. The question of whether an "efficient enough" algorithm may be written to defeat a "proficient amateur" in "reasonable" time on "realistic hardware" cannot be formalized. It is interesting, but belongs in the intersection of engineering and algorithms, not computer science. NTK 14:15, 13 April 2007 (UTC)

When considering a board of variable size n, GO is a PSpace-complete problem. There are attempt to cope with such problems not by always solving them but by finding randomized solutions, approximate solutions, etc. Maybe we should keep the problem but change its formalization. APH 06:42, 15 April 2007 (UTC)

There is no formalization, this is fairly meaningless in the context of Computer versus Human. Neither a human nor a computer can play Go on an infinite board. For very large n it would be easy for the computer to beat a human with a simple strategy based on sheer memory and endurance. For bounded n, the problem is again O(1). Clearly computer go in practice is a very hard, interesting, and unsolved engineering problem involving all the techniques you describe and more, but this is not a theoretical problem of computer science.

In any event, if you can actually formalize what a human go player is in the language of computer science, you will have accomplished something a lot bigger than computer go. NTK 01:34, 18 April 2007 (UTC)

Go is a PSpace Complete problem. You will get O(1) problems only if you don't restrict memory or build a special program for every n. Note That if you allow constructing a special program for every n you become so problem that you can solve problems like the halting problems. Coping with problems of high complexity class (even like just NP-Complte) happens a lot in practice. A solution that will be able to cope with the well (e.g., Showing P=NP)or proofing that one cannot cope with the problem is very interesting theory question. Again, I agree that the problem definition should be changed. On the other hand I think we should keep the problem. APH 05:35, 18 April 2007 (UTC)

[edit] Artificial Intelligence

Source:

In the article "Prospects for Mathematical Logic in the Twenty-First Century", Sam Buss suggests a "three-fold view of proof theory" (his Table 1, p. 9) that includes in column 1, "Constructive analysis of second-order and stronger theories", in column 2, "Central problem is P vs. NP and related questions", and in column 3, "Central problem is the "AI" problem of developing "true" artificial intelligence" (Buss, Kechris, Pillay, Shore 2000:4).

"I wish to avoid philosophical issues about consciousness, self-awareness and what it means to have a soul, etc., and instead seek a purely operational approach to articial intelligence. Thus, I define artificial intelligence as being constructed systems which can reason and interact both syntactically and semantically. To stress the last word in the last sentence, I mean that a true artifical intelligence system should be able to take the meaning of statements into account, or at least act as if it takes the meaning into account." (Buss on p. 4-5)

He goes on to mention the use of neural nets ~~(i.e. analog-like computation that seems to not use logic -- I don't agree with him here: logic is used in the simulations of neural nets -- but that's the point -- this stuff is open).~~ Morever, can ~~I am not sure that~~ Buss can eliminate "consciousness" from the discussion? Or is consciousness a necessary ingredient for an AI?

Description:

Mary Shelley's Frankenstein) and some of the stories of Edgar Allen Poe (e.g. The Tell-Tale Heart) opened the question. Since the 1950's the use of the Turing Test has been a measure of success or failure of a purported AI. But is this a fair test? [quote here?] (Turing, Alan, 1950, Computing Machinery and Intelligence, Mind, 59, 433-460. http://www.loebner.net/Prizef/TuringArticle.html

A problem statement requires both a definition of "intelligence" and a decision as whether it is necessary to, or if so how much to, fold "consciousness" into the debate.

> Philosphers of Mind call an intelligence without a mind is a zombie (cf Dennett, Daniel 1991, Consciousness Explained, Little, Brown and Company, Boston, ISBN 0-316-180066-1 (pb) ):

A philospher's zomie, you will recall, is behaviorally indistinguishable from a normal human being, but is not conscious. There is nothing it is like to be a zombie; it just seems that way to observers (including itself, as we saw in the previous chapter). (italics added or emphasis)" (Dennett loc cit:405)

Can an artificial, mindless zombie be truly an AI? No says Searle:

"Information processing is typically in the mind of an observer . . . the addition in the calculator is not intrinsic to the circuit, the addition in me is intrinsic to my mental life.... Therefore, we cannot explain the notion of consciouness in terms of information processing and symbol manipulations" (Searle 2002:34). "Nothing is intrinsically computational. computation exists only relative to some agent or observer who imposes a computational interpretation on some phenomenon" (Searle 2002:17).

Yes says Dennett:

"There is another way to address the possibility of zombies, and in some regards I think it is more satisfying. Are zombies possible? They're not just possible, they're actual. We're all zombies [Footnote 6 warns not to quote out of context here]. Nobody is conscious -- not in the systematically mysterious way that supports such doctrines as epiphenomenalism!"((Dennett 1991:406)

> Gandy 1980 throws around the word "free will". For him it seems an undefined concept, interpreted by some (Sieg?) to mean something on the order of "Randomness put to work in an effectively-infinite computational evironment" as opposed to "deterministic" or "nondeterministic" both in a finite computational environment (e.g. a computer).

>Godel's quote: "...the term "finite proceedure" ... is understood to mean "mechanical procedure". concept of a formal system whose essence it is that reasoning is completely replaced by mechanical operations on formulas" ... [but] the reuslts mentioned in this postscript do not establish any bounds for the powers of human reason, but rather for the potentialities of pure formalism in mathematics."(Godel 1964 in Undecidable:72)

Importance:

> AC (artificial consciousness, an AI with a feeling mind) would no less than an upheavel in human affairs

> AI as helper or scourage or both (robot warriors)

> Philosophy: nature of "man", "man versus machine", how would man's world change with AI's (robots)? Will it be good or an evil act to create a conscious AI? What will it be like to be an AI? (cf Nagel, Thomas 1974, What Is It Like to be a Bat? from Philosophical Review 83:435-50. Reprinted on p. 219ff in Chalmers, David J. 2002, Philosophy of Mind: Classsical and Contemporary Readings, Oxford University Press, New York ISBN 0-19-514581-X.)

> Law: If conscious, does the AI have rights? What would be those rights?

Current Conjecture:

An AI is feasible/possible and will appear within this century.

This outline is just throwing down stuff. Suggestions are welcome. wvbaileyWvbailey 16:13, 6 September 2007 (UTC)

The central question for computer science is: Can every aspect of intelligence be simulated by a machine? (See the rewrite in progress of philosophy of artificial intelligence) ---- CharlesGillingham 08:59, 10 October 2007 (UTC)

[edit] Quantum Computers and Classical Computers

What does everyone think about adding the following problem to this list: "Are quantum computers more powerful than classical computers?" Or, in other words, "Is BQP a subset of P?" For example, the best known algorithm for integer factorization on a quantum computer is polynomial-time, while the best known algorithm for factorization on a classical computer is slower than polynomial time. However, it has never been proven that a classical polynomial-time factorization algorithm could not exist. See number 3 on this page: http://www.scottaaronson.com/writings/qchallenge.html. Also see Integer_factorization#Difficulty_and_complexity. I didn't want to immediately add this problem to the list without discussing it, considering the debate about other problems on this talk page. Also, I'm not even close to being an expert on quantum computing or complexity theory. :) --Navigatr85 17:37, 13 August 2007 (UTC)

This comes up in the paper by Buss, Kechris, Pillay and Shore (see the Church-Turing question). They specifically ask:

"What are the relationships among the classes P, NP, PP, BPP and so on?"

On page 12 of the article is a drawing that shows "Quantum computing" under "probabilistic computation". The name "Deutsch" seems to appear again and again: e.g. a couple references in the paper, including D. Deutsch, "Quantum theory, the Church-Turing principle and the universal quantum computer", Proceedings of the Royal Society A 400(1985) 97-117. I am not familiar with any of this other than (very) cursorily, but the question of "the power" of "analog computation" as well as "quantum computation" seems to come up again and again. Does this fall under the Church-Turing Thesis question? I dunno; I don't think it should necessarily. My guess is this is a decent question if you can figure out how to frame it properly and support it with sources. Don't be shy. The critics on this discussion page have been too picky and fussy, in my opinion. wvbaileyWvbailey 03:45, 14 August 2007 (UTC)

The infinite-resource quantum computer is Turing complete. However, research in Quantum finite automata has shown that certain classes of QFAs are more complex than DFAs, which represent our limited-resource classical computers (they can parse certain context-free languages and context-sensitive languages). SamuelRiv (talk) 09:19, 21 November 2007 (UTC)

[edit] Algorithm: what is such a beast?

This is a holding place for the following. The intent is not to push this or any other point of view, but to make the question evident. A number of epistomologic and mathematical issues bubble up from this:

from https://research.microsoft.com/~gurevich/

[164] Andreas Blass and Yuri Gurevich

"Algorithms: A Quest for Absolute Definitions"

Bulletin of the European Association for Theoretical Computer Science

Number 81 (October 2003), pages 195-225.

Reprinted in Chapter on Logic in Computer Science

Current Trends in Theoretical Computer Science

World Scientific, 2004, pages 283-311

Reprinted in Church's Thesis After 70 Years

Ontos Verlag, 2006, 24-57

See more details here

What is an algorithm? The interest in this foundational problem is not only theoretical; applications include specification, validation and verification of software and hardware systems. We describe the quest to understand and define the notion of algorithm. We start with the Church-Turing thesis and contrast Church's and Turing's approaches, and we finish with some recent investigations.

wvbaileyWvbailey 00:48, 5 September 2007 (UTC)