Talk:Hypercomputation

Kevin baas said, took out b%llsh@t and inserted usefull categorization.

The b%llsh@t in question was:

[Hypercomputation with real valued analogue computing] might require quite outlandish laws of physics (for example, a measurable physical constant with the value Ω).

Kevin, what are you talking about? Are you suggesting that analogue computers, in general, can solve the Halting problem? If so, citing a proof would be handy! If not, then the text should remain.

I am not suggesting that physics actually has improbable properties like this -- just that they would be necessary, if, as I believe some articles in the literature have suggested, analogue computers could be hypercomputers. -- Pde 04:22, 9 Sep 2003 (EDT)

My understanding, as a computer programmer, of the word "hypercomputation", is a machine that can "solve problems" in less computation time than a turing machine.

This is not the way the term is used in the literature. As the article explains, "hypercomputation" refers to computing non-recursive functions -- ie, those which cannot be computed by Turing machines. Many things can solve problems faster than Turing machines. Stylised real computers (eg register machines, or programming languages with no memory bounds) can do O(1) memory access, which Turing machines cannot. Quantum computers do polynomial factorisation, sqrt(N) unsorted search, etc. Non-deterministic Turing machines, which probably don't exist in reality but are nontheless mathematically interesting, are much faster than Turing machines (how much, depends on whether P=NP). These devices are not hypercomputers, and cannot even solve the halting problem, let alone any of the harder decision problems in the arithmetic hierarchy. -- Pde 00:09, 16 Sep 2003 (UTC)

"Less computation time" means 'much' faster, as you have stated. I did not say "less time", I said "less computation time", which is a different statement altogether. A turing machine cannot solve a problem in "less computation time" than any other turing machine. For instance, it cannot solve an E problem in P time. A machine capable of doing this would, by definition, be a hypercomputer. It has been demonstrated that a pulse computer is, in this sense, a hypercomputer. Perhaps if you had read what I wrote before, you would be aware of this fact. I'm sorry that it doesn't agree with your point of view. -Kevin Baas

Kevin, reading your comment, I believe that you haven't understood everything I've been saying. I'll try to work out where this is... (reads)

Aha! bingo. I think I've found the issue. When I said "cannot be computed by Turing machines", you took me literally. What I should have said, was "cannot be computed by Turing complete systems".

All the stuff about other kinds of faster-than-turing-machine computation (ordinary quantum computers, O(1) memory access, nondeterministic turing machines, pulse computers) is important, but none of it is hypercomputation. -- Pde 00:34, 17 Sep 2003 (UTC)

Ordinary quantum compuers are not super-turing. They are multi-tape turing machines. (i.e. parrallel processing architecture) To the extent that a quantum computer has a finite storage capacity, it has finite parrallel processing capability. Up to the point where all processors are in use, the machine would appear to be computing 'faster-than-turing', because as the problem size grows, more processors (that weren't being used before) are being put to use.

Furthermore, you misunderstood my remark on the superposition of states in a quantum computer. If I have a set of, say, 3 elements, that set has exactly 7 possible nonempty subsets: {{1},{2},{3},{1,2},{2,3},{1,3},{1,2,3}}. If I have a set of say, 256 elements (the number of possible states of a byte), the number of nonempty subsets is finite. Indeed, if I have a finite set of states, the number of possible subsets, or "superpositions" (to use the quantum mechanical sense), is finite. There is no such thing as an infinite superposition. Such a phrase is completely absurd.

I think you might want to do some more reading or study on this. Basis sets for function spaces are always at least countably infinite. In the context of QM, I asked some physicists about this, and couldn't think of any spatial (as opposed to spin) Hamiltonians which *didn't* have infinite numbers of energy eigenvectors.

I also think your understanding of superpositions is incorrect. Superpositions involve not only a subset of the possible states, but a coefficient for each state; to run with our example, a superposition can be 1.0 x {1}, or 0.3 x {1} + 0.7 x {2}, etc. Each of these is a real, distinct quantum state (just not an eigenstate of the operator in question). -- Pde

Ah! I've found it! (give me a break.) I'm not familiar with the term "turing complete", unless you are refering to a "universal turing machine", which, as turing proved, is just a regular turing machine. Could you briefly explain this term to me?

Consider a computational system C, computing a value v from program p and input i (ie <math>v = C(p, i)<math>). C is said to be Turing-complete if there exists a program <math>p_{Turing}<math> such that for any Turing machine T within inputs <math>i_T<math>, encoded in a standardised manner, <math>C(p_{Turing}, T + i_T) = T(i_T)<math>. The same must hold true in reverse (ie, every universal Turing machine has a program <math>p_C<math> which emulates the operation of C for all inputs). Each Turing-complete system can compute the same set of functions. Some commonly discussed examples of Turing-complete systems: register machines, reductions in lambda calculus and horn clauses, universal Turing machines, idealised programming languages.

Note that this kind of computability theory is just concerned with what functions can and cannot be evaluated, rather than how "fast" the computational systems are (speed is studied in computational complexity theory). --Pde 05:42, 28 Sep 2003 (UTC)

Again and again I have to make the point: The problem is not "solving the problem" per say, but solving the problem in X time; how fast the machine converges to a solution. Whether that time be polynominal, exponential, infinite, ect. (...)

Well, computability theory, as it appears in textbooks and academic journals, is defined to be about whether a function can be evaluated in a finite time. Please note also that "solving a [mathematical] problem" is defined to mean "evaluating a function". This is not the same as the everyday expression "solving a problem".

I am not talking about computability theory. I am talking about computational complexity theory. You're the one talking about computability theory. Look, if hypercomputer is really defined as you say it is, which I'm sure the people at [www.hypercomputation.org] would dispute, then it desperately needs either to be redefined or not taught, because it takes the wrong approach.

(...) When I mention going from one computation complexity class to another, I'm not talking about a "faster" turing machine, I'm talking about something that is impossible on a turing machine (i.e. a turing-complete system). I'm talking about, for instance, solving an E problem in P time. Now a computer doesn't "solve a P problem", rather, it "solves a P problem in P time." (or a continuous problem in infinite time) When one refers to "solving a problem", they are making a time/complexity-differential statement; they are discussing related limits. (limit-theorems) This is a qualitative statement.

Efficiency is of course a subject of real interest. As I said, it is studied in computational complexity theory. But hypercomputation is not a part of computational complexity theory.

Also, your claim "I'm talking about something that is impossible on a turing machine (i.e. a turing-complete system). I'm talking about, for instance, solving an E problem in P time." is, wrong. Example 1: it is currently believed that prime factorisation is an Exp-time problem on Turing machines. But ordinary quantum computers can solve it in P-time. Ordinary quantum computers are Turing-complete systems.

Example 2: A computer whose clock rate doubles every second. Such a hypothetical device can, by definition solve any E problem in P time. It is also a Turing-complete system.

Kevin, are you finding it hard to understand my claims? If so, you should be trying to learn about the subject, before you write about it. Or are you having trouble with the fact that mathematics is constructed through fixed, almost-arbitrary definitions? In which case, you should think long and hard about why mathematicians rarely find this problematic. -- Pde 00:28, 30 Sep 2003 (UTC)

I'm having trouble with your innane patronizing and concieted attitude. I'm also having trouble communicating with you, but this may in fact be the same problem.

I'll have you know that my spatial-mathematical I.Q. is over 150 (my overall I.Q. is over 130), I scored the highest in my school on the AHSME, and was the first student in my school in at least ten years to be invited to take the AIME. My "spatial reasoning" skills were tested by the GATT tests to be at or above the 99.9th percentile. (One standard deviation below that was the 99.8th percentile.) I scored a 5/5 on the A.P. Calculus exam (BC), and a 5/5 on the A.P. CompSci exam (AB). (Funny, I didn't take any computer classes in high school.) You should really be more carefull who you're addressing before you insult their intelligence.

I find it very telling how you only address small parts of my argument, leaving the rest as valid by default. Indeed, you evade the core of my argument with random precision. --Kevin Baas

(P.S. If by "turing complete", you mean a turing machine with qualitatively infinite processing time and storage capacity, then you are speaking of something that is no longer a turing machine.)

You seem to be using a paradigm that is ill-suited to the problematic. You are looking at the problem structurally, when it is a problem of dynamics.

Formal systems only exist by way of dynamical systems. They are not abstract entities that exist in-and-of-themselves. When we are considering a "machine" we are considering a dynamical system, not a formal system. Our assesments and theories are only valid with respect to dynamical systems, regardless of whether our machine is physical or theoretical. -- Kevin Baas

Solving a problem in less computation time than a turing machine is itself a problem, and one that a turing machine is incapable of solving. Therefore, this is a problem that a turing machine can't do.

If a super-turing machine is not a hypercomputer, then we find ourselves lacking a term for a very important class of machines. -- Kevin Baas

How would it do this? Well, first, since each 'algorithm' or 'formula' is actually a number (godel numbering), it would have to be able to "compute" a larger set of numbers than a turing machine. It would have to "compute" uncomputable numbers.

But what do we really mean by "compute"? To understand hypercomputation, one must re-evaluate this term, and deconstruct the computer.

But to make a long story short, an analog computer, like a digital computer, is a dynamical system. However, the digital computer is a special case analog computer, which only uses a subset of the possible attractors - only point attractors or point-periodic attractors. These are the "computable numbers". An analog computer which is not restricted to the range, can manifest strange attractors as solutions. (Strange attractors are stable.) In a sense, these strange attractors are the "uncomputable numbers".

One would require quite outlandish laws of physics to refute this. The question is how to design a programmable analog computer that computes in a usefull manner with these "strange attractors".

But hypercomputation is not limited to analog computers. As I have listed, they also include pulse computers, which are simpler and for now more practical than analog computers. Some simple operations have been performed with pulse computers, including common computer science problems like searching, sorting, and linear optimization.

Pulse computers have consistently computed some of these problems in less computation time than is possible with a turing machine, making it, by definition, a hypercomputer.

-Kevin Baas

Kevin Baas wrote:

I'm having trouble with your innane patronizing and concieted attitude. I'm also having trouble communicating with you, but this may in fact be the same problem.

I hope not, but I guess it's possible. Despite my genuinley patronising attitude, I am spending a lot of time explaining things to you.

It doesn't really matter how smart you are. If you aren't able to work within the same frames of reference as other intelligent people interested in the same problems, and build on their achievements, you'll find yourself reinventing wheels-- and wasting your own and other people's time.

I find it very telling how you only address small parts of my argument, leaving the rest as valid by default. Indeed, you evade the core of my argument with random precision. --Kevin Baas

I never claimed that everything you've said is wrong. But you've got so many important things wrong that it's seriously problematic. The thing about mathematics is, even small differences in definition or errors in inference lead to completely inconsistent conclusions.

(P.S. If by "turing complete", you mean a turing machine with qualitatively infinite processing time and storage capacity, then you are speaking of something that is no longer a turing machine.)

Turing machines are abstract mathematical constructs with unbounded amounts of time and storage. As long as there exists *some* finite amount of each within which each value of a function can be evaluated, the function is said to be recursive or decidable or Turing computable, often abbreviated to "computable". Interestingly, if you move from unbounded resources to resources which are actually infinite, you are able to evaluate a huge (infinite, actually) set of functions which are non-recursive -- that is, questions which Turing-complete systems could never answer. Such as: what is the fiftieth Busy Beaver (http://grail.cba.csuohio.edu/~somos/bb.html) number? No turing machine, no silicon computer, no qubit computer, no pulse machine or other analogue computer whose design I'm aware of can ever tell you that number. But hypercomputers, if they existed, could do so.

You mentioned subtle distinctions, I've always understood "infinite" to mean "unbounded", making it a qualitative distinction: the distinction between bounded and unbounded. The difference between the distinctions that you made between 'unbounded' and 'infinite' seem to be a hidden conceptual trick: by infinite, you seem to imply that one can measure a result that requires infinite time,

Correct.

Well then, this is a logical error.

Not exactly, although it is a good example of why it's pretty damn unlikely that hypercomputation will turn out to be possible. But, read the article for some unlikely ways around this which people have dreamt up. If there is a way to perform an infininte number of computational operations in a finite part of physical spacetime, then that could lead to hypercomputation. -- pde 07:28, 23 Dec 2003 (UTC)

No, it is a logical error. You seem to be skewing the interpretation so that it becomes something familiar to you, and responding with a learned construct. And btw, I don't care about people's delusional fantasies. And ya, hypercomputation insofar as it deals withn infinite lenght bit string of finite lenght, is impossible. But let's not deal with absurdities here. We are talking about zero-dimensional information or one-dimensional information or somewhere inbetween. We are not talking about zero-dimensional information with properties of one-dimensional information. But I digress, one cannot, by any measure (no pun intended), measure a result in finite time which by definition takes infinite time to measure or occur (same difference anyways). That is absurd.

whereas by 'unbounded' you imply that measurements can only be ephemereal.

Incorrect. What I mean is that, for a universal Turing machine T computing a function <math>f(x)<math>, for each x, there exists a finite amount of memory and time in which <math>f(x)<math> can be evaluated. These are "unbounded" because they are associated with the f and the x, not the T. -- Pde

Thank you for the clarification. That usage of the word is confusing to me because it states something that I trivially assume. Also, because it's redundant: "abstract mathematical construct" implies, or, rather, asserts "unboundedness".

In any case, you imply the concept of information insofar as you imply the problem of measurement, which brings me to the second part of my response...

Regarding what hypercomputers can do and what is possible: yes and no. "A number", that is, a symbolic expression of a point in a phase space, is necessarily a discrete entity, for when we say symbolic we imply that there is a finite set of symbols (if the set where otherwise, we would use a different word, and a different concept.), thus the only way for the "number" to transcend the set of computable numbers, would be for it to be represented, in it's most reduced form, as an infinite string of symbols. Now can create sets of symbol strings, and represent each set by a new symbol, thus creating a much larger symbolic set that can express the same information with less symbols. (you can use shannon's information theory to calculate the information in each symbol, and you can represent this relationship in terms of information) So long as the sub-strings are of finite lenght, and their symbols are from a finite set, any set of strings that we translate to a new set of symbols, as discussed, remains of finite size. However, when we introduce an infinite string, the mentioned set becomes an infinite set. No matter how we break down the set, or the string, we still have an infinite set. In the same way we can not reach an infinite set starting with finite sets. Therefore, when we are dealing with the an infinite set or an infinite string of symbols, the concept of number that we are familiar with - a string of symbols - is inappropriate.

the third part of my response: when we speak of computers in the contemporary sense, we must adapt our paradigm: God is dead. Computers are dynamical systems, and must be understood and discussed as such, and in terms of such. Anything else is meaningless. --Kevin Baas

Poor judgement

Kevin, you're showing a lot of mathematically uninformed arrogance here. Do the math. There are about 300 million Americans. 99.9th percentile means that you're one in a thousand, which sounds pretty nice on the surface. Of course, that means that there are 300,000 Americans alive right now who are as good or better than you in spatial reasoning. Isn't awfully prideful to assume that you have a better grip on the math of hypercomputers than all 300,000 of them? Especially when you consider that you have taken any formal courses in the math behind them? Sure, you may have read some articles and a book or two, but it's hard to believe that laboring by yourself you out did all those who came before you on the subject of hypercomputing. Now, bear in mind that these 300,000 represent only the Americans on equal footing with you today and that most of them are older than you--that is they've had more time to study the mathematical nuances of "unbound" v. "infinite," etc. OK, I'll give that most people don't much cotton to hypercomputing. So of the 300,000 how many do you suppose have set their hands to it? 1 in 100? 1 in 1,000? 1 in 10,000? In any case, you still have yourself a churchful of folk who are well up to your level on the subject, even without the head start in years that most of them have. I'm not saying this to suggest that you can't do anything personally, but I do think that you should consider that as someone relatively new to the scene, you should sit back and come to fully understand what's been said before you throw in your two bits. If you don't... Well-- you come off like someone who is mathematically ignorant, not just of the topic at hand, but of elementary percentages. I'm saying this not to make you upset, which if I were you (and I was) I would be. I'm saying this so that you can get rid of this pride before it does you damage some place more serious than an internet forum. If you bring this to an interview or an application, whoever is looking at you will reject you, not because they don't think your smart, but because they don't think you have used your smarts to make some important deductions about the world around you. The number one deduction being, of course, that those before you might have thought through some of the problems you're just starting to consider... Just think about it, OK?

I'll have you know that my spatial-mathematical I.Q. is over 150 (my overall I.Q. is over 130), Who the f*ck cares. So called "smart people" make huge mistakes all the time - oftentimes as a result of being blinded by arrogance and over-confidence. I've found that most of my university instructors are often wrong and biased. BTW, I have an IQ of 145 and makes stupid mistakes all the time (childhood test, so I may have lost a few neurons since then - would explain a few things). --mav

Thanks mav. ;-) I agree. My point was not to be arrogant, it was rather to block what I percieved (with good reason) to be a rather shameless decay of diplomacy on the part of PDE. To restate what I've just said: I do not by any means consider myself an "elite". I simply believe that I deserve a prudent degree of consideration and civility, as opposed to rash assumptions and low-class remarks. --Kevin Baas

The phrase "compute directly on real numbers" is inaccurate and misleading. A "number" is a symbolic string. Any system that computes with symbolic strings ipso facto works with zero-dimensional information, and is thus a turing machine. I.e. not a hypercomputer. -Kevin Baas 2003.12.22

This statement is incorrect. It is entirely possible to have a hypercomputer which has only finite strings as inputs and outputs. There would have to be some infinite stuff (or magic), going on in between though. -- pde 06:41, 23 Dec 2003 (UTC)

That may very well be the case PDE, in fact, I think what you're talking about is called a "computer", and the magic stuff you're talking about is a surjective mapping, manifested in the nonlinear dynamics of an electric circuit. A new input pushes perturbs the system, and the system settles back into an attractor (in a discrete dynamical system (i.e. a digital computer) this attractor is (for practical purposes) a periodic point attractor), thereby changing it's state as it dissipates the energy. Thus it "computes".

(new)Let me add: I assume first, ofcourse, that you forget to add the assertion taht said finite string input/output system is working with inputs and outputs in discrete time. But ofcourse this is the case, as you said "string" and thus implied that the timing of the symbols was irrelevant. (that it is not a pulse computer)

Granted that, you have neglected programmability. Ofcourse, to perform such "hypercomputations", the system would have to have an internal state space (memory) with an informaion dimension greater than zero. But to write a computer program that utilizes the attractor set of this expanded phase space, with only discrete-signal discrete-time input, would require infinite time, as it would require an uncountable number of symbols to transcend the set of possible programs in a turing machine. I imagine that a "hypercomputer" is by definition programmable, and thus can be programmed in finite time. If it is not programmable in finite time, then nothing can use it. If nothing can use it than by no measure does it manifest itself as a hypercomputer. If a "hypercomputer" must by definition be programmable (which, as pointed out in the last sentence, is neccessary in order for the term to be at all meaningfull), then a hypercomputer with finite strings as input and output is logically impossible. -- Kevin Baas 09:40, 12 Jan 2004 (UTC)

In any case, it's quite off-topic. The topic is the phrase "compute directly on real numbers", esp. in regard to nueral networks. Neural networks do not store information in any base, binary, digital, etc. That is, they does not store "numbers", rather state is preserved(and updated) via feedback loops between neurons. One might say that the state is stored in "real weights". This depends on the type of nueral network. But no neural network stores numbers. If there are numbers stored anywhere in the circuit, it is ipso facto a hybrid circuit. -Kevin Baas 2003.12.23

Hi Populus, I was just wondering, when you refer to the models of neural networks with " the ability to carry out computations with exponentially lower complexity than standard Turing machines" — are those systems just equivalent to non-deterministic Turing machines? If that is the case, the term "super-Turing computation" is being applied both to machines which are hypercomputers and to machines which are able to solve NP problems in P time, and that fact should be noted in the article. -- pde 07:17, 23 Dec 2003 (UTC)

I'm just pulling in some of User:Kevin baas's text from the former Super-Turing computation article. The intent was to combine all the articles on machines that violate the Church-Turing thesis (including the polynomial-time version) in one place. Populus 12:32, 23 Dec 2003 (UTC)

Populus, do me a favor and look up Church-Turing thesis. -Kevin Baas 2003.12.24

Ok, Kevin, do you have a citation to the article(s) which introduce those "exponentially lower complexity" neural networks? -- pde 23:30, 23 Dec 2003 (UTC)

I don't know where you're getting "exponentially lower complexity" from. You seem to have your computational copmlexity classes mixed up. I do remember some resources. I'll look them up after the holidays. But that's completely besides the point. The point is that, as you said, such a machine is not a hypercomputer, yet is more powerfull than a turing machine. Yet, the computational complexity page supposedly links to machines which are more powerfull than turing machines. Perhaps we should make a page for machines which are more powerfull than turing machines then? -Kevin Baas 2003.12.24

I can asure you, Kevin, that I do not have any complexity classes mixed up. And I'm quoting those words from the current article text, last clause of the first paragraph. According to Populus, (s)he was just importing something you'd written. Looking at the super-Turing computation page history, I now see that he was interpreting what you'd written. But Populus added an implication that the term was used in this way in the nerual networks literature. I want to know if this is the case, and if so, where, because the meaning is obviously quite different if it reaches beyond computability theory and into complexity theory.

Of course you can make a page for machines which are faster than Turing machines, if you think you're up to it. Be sure to define carefully what kind of Turing machine you take as your baseline, including alphabets and state graphs (also remember, ordinary Turing machines cannot do O(1) memory lookup), and include non-deterministic Turing machines and quantum computers as prominent examples. -- pde 23:42, 24 Dec 2003 (UTC)

OMG, I'll be sure to include my name, age, and address as well. Maybe then it'll be an academic article. That way it won't be pedantic and miss the point entirely. And I'll be sure to wear my safety googles, Mrs. Smith.

In the mean time, I'll blurt out keywords like O(1) memory lookup to sound smarter than the person I'm talking to. (shhh... they're actually really simple concepts.) -Kevin Baas

Retrieved from "https://academickids.com:443/encyclopedia/index.php/Talk:Hypercomputation"

Talk:Hypercomputation

Poor judgement

Navigation

Search

Toolbox

Personal tools