FAQ 
Calendar 


#601




Quote:
I'm of the opinion that if a thing is computing, then it's computing. If a thing is Turing complete, it's Turing complete. These terms are objective descriptions about the state and properties of the object, not subjective assessments. If a device is Turing complete, then that device is Turing complete even if it's locked in a drawer. The fact that you can't get to it and fiddle with its inputs is utterly irrelevant to the device's status as a Turing complete device. Perhaps it will help you understand my problem with your approach if we avoid something so hard to define as "computing". So instead let's suppose we're debating whether a system is breathing. I'll assert that all living people breathe. With me so far? Suppose we put a person in a box and let you talk to him through an open window in the box. At this point you'd agree that the system you're interacting includes an element that is breathing, right? You can totally see him doing it, and you can see him acting in ways that no nonbreathing (dead) person could. Now suppose we close the window and tell you that you can now only interact with the box via a switch and a light, mounted on opposite sides of the box. If you turn the switch to the "on" position, then by the time you walk around to the other side of the box the light will be on. If you set the switch to "off", then by the time you walk around to the other side of the box the light will be off. In other words, the behavior of the box no longer requires a person to be inside it, and somebody who didn't know there was a person in there could not prove it by interacting with the box. My position is that the system still includes a breathing element, because there's still a person in there. Your position appears to be that since you can't prove that contents of the box include a breathing person by its behavior, that any people who happen to be in there aren't breathing! 
#602




Quote:
Now, at any given time this program and all its data and state information consist of an enormous string of bits in the computer's memory, and its execution trace can be represented as a finite set of state transitions over that time (not Turing complete). It could be drawn as an enormous state transition diagram. So what's the value of having Turingcomplete precursors  the Turingcomplete specification language that created it and the Turingcomplete platform that executes it? It's because we don't (except in special cases) intentionally build finite state machines per se, what we build are logical descriptions that reflect the way we think about the world, and the essential function of computers is to instantiate those descriptions in a completely general way. The premise of CTM is that cognition also works in a completely general way using exactly parallel kinds of operations. As for your challenge in the last paragraph I quoted, I find it strange that you claim I "keep missing" some point whereas ISTM that it is you who is missing it. The premise of some "extended capabilities" in one system versus another when both are performing identical tasks is an obfuscatory fiction. If they are performing identical tasks then they are identical Turing machines. Turing completeness implies no specific functional capability other than what is inherent in any Turing machine, and reflects the nature of a Turing machine to be able to simulate the fixed computation of any other. In the real world, Turing completeness in a real computer is reducible to (I believe) a minimum of four instructions, ignoring the contrived silliness of oneinstruction computers. The question is meaningless here, too, because no nontrivial program could run on a computer that lacks a Turingcomplete instruction set. As I mentioned before, a Turing completeness is both fundamental but at the same time actually a pretty low bar. As an exercise for myself  ignoring here the silliness of oneinstruction computers  this is my first take on such minimalism; I'm pretty sure that a real computer with just the following four instructions would be Turing complete, and I challenge anyone to write any meaningful program at all without these operations. This ought to definitively answer the question of why a computer's instruction set needs to be Turing complete. And given that I'm pretty sure this is Turing complete  that these instructions can literally perform any computation that is computable or any logical operation imaginable  my challenge back to you is to tell me what awesome "extended capabilities" are present here! ADS (add memory location to register, and skip if not equal to zero) DCR (deposit register to memory and clear register) JMP (jump to specified location) AND (AND memory with register) Quote:
An embedded microprocessor (LBA) in isolation is itself Turing complete of course, no argument about that. But its functional role in the larger system in which it's embedded is limited by the functionality exported by the interface of its fixed software; nothing else is available. It's the classic "black box", nothing more, no matter what's inside it. So a system the implements Turingcomplete functionality, like one that uses its embedded microprocessor to implement a LISP interpreter, is Turing complete, but one which uses it to implement a basic calculator is not. I find that I'm repeating myself, but I trust that makes it clear, or at least clearer. 
#603




Quote:
Quote:
This also illustrates my example. Any valid BlooPprogram is also a valid FlooPprogram; the extended capabilities come in the form of an additional 'muloop' instruction. More generally, any recursive set can be decided by a nonTuring complete automaton (a machine that's guaranteed to halt). This class contains very nontrivial sets, such as the prime numbers, the Fibonacci numbers, and many others, all of which can be computed using a BlooPlike language. Quote:

#604




Quote:
Pattern matching using pushdown automata: http://www.stringology.org/papers/Zd...hesis2010.pdf The list of nontrivial programs that can be written using nonturing complete instruction set is enormous (and that is an understatement). 


#605




Regarding the need for a UTM (limited by memory of course):
Consider a machine with the following attributes: 1  1,000,000,000,000,000 times the memory of the max memory of a human brain 2  A turing complete instruction set with one exception: the completion of each instruction involves a check if every memory element has the value 27, and if this is true it changes the first memory element to 28. This machine is capable of computing many functions that the human brain can't (due to increased memory) but it can't compute all computable functions that a UTM is capable of (at minimum it can't compute any function that ends with all memory elements set to 27). 
#606




Quote:
The salient point about Turing completeness, again, is the following: We don't (except in special cases) intentionally build finite state machines per se, what we build are logical descriptions [i.e. programs] that reflect the way we think about the world, and the essential function of computers is to instantiate those descriptions in a completely general way. The premise of CTM is that cognition also works in a completely general way using exactly parallel kinds of operations. Quote:
You might want to rethink your claim of falsehood since if you read more carefully, that is clearly not at all what I said. All of these things  regular expressions, or the SQL and HTML examples you mentioned earlier  are all generally dependent on underlying software and hardware layers that are, in fact, programs specified in Turingcomplete languages running on hardware platforms with Turingcomplete instruction sets. No doubt there are some specialcase exceptions, but the preceding is overwhelmingly the general case. I note that you failed to either quote or respond to my challenge in #602: what "extended capabilities" do you find in these four instructions that I believe constitute a simple but Turingcomplete instruction set that could be dispensed with and still produce a generally useful computer? Is it clear why each of these functions is essential for computability  for the Turing sense of having "computational" capacity? 
#607




Quote:
Quote:
Your point is false. 
#608




Quote:
However, you seem to want to reject both options; but this is inconsistent. Here, you affirm the equivalence between LBAs and FSAs: Quote:
Quote:
Quote:
Quote:
And of course, there are all the programs you can write in BlooP, which can be executed on a computer that isn't Turingcomplete. The example also makes clear, I had thought, what I mean by 'extended capabilities': add an unrestricted loop instruction (yielding FlooP), and you jump all the way to Turing completeness. But that doesn't mean that programs that don't use this instruction aren't properly 'computations'yet, they're programs that could be run on a nonuniversal machine. Last edited by Half Man Half Wit; 07282019 at 04:00 AM. 
#609




Quote:
That a finitestate machine representation of any specific program running on a computer is not Turing complete while being computationally equivalent to such a program is not a particularly interesting fact, since the FSA just an abstraction that only represents the capabilities of the computer when it's running that specific program. (Although the FSA would, in fact, be Turing complete if it happened to be an interpreter for a language that was itself Turing complete.) It is precisely the distinction between a Turing machine and a universal Turing machine. Hence, regarding your first point, the equivalence between LBAs and FSAs is not in contradiction to the premise that LBAs must be Turing complete in order to achieve the computational capabilities required for cognition. One might argue about whether that premise is true or not, but it's not contradicted by LBAFSA equivalence. Perhaps your perception of a contradiction is in the fact that both the LBA and FSA are obviously performing the same computation, but that isn't the point. The point is the premise that the underlying mechanisms of cognition don't have a fixed function, but operate like a general purpose computer that can implement any computable function (and conversely, that therefore cognitive processes can be instantiated on any LBA with suitable capacity). I think we've thoroughly exhausted this topic by now, but I wanted to make one final effort to explain my argument. 


#610




Your argument is sufficiently clear, it's just wrongif there exists an equivalent FSA for a given computation, that computation can be performed by a machine lacking a universal instruction set, for instance, one that merely executes bounded loops, like BlooP.

#611




Quote:
I know this thread is basically dead at this point, but I thought I would explain my post that you considered condescending. There were two possibilities: 1  You were not aware that a calculator has a general purpose processor or 2  You were aware of that fact and you were going to continue to believe that it wasn't computation even though that position means that two systems that are the same in all significant respects are different from the perspective of computation (meaning computation is not based on a physical attribute) Option #2 is the far worse assumption. I believe begbert called that position "insane". I considered both positions and because of how far out in left field position #2 is, I made the more favorable assumption about you, that you just didn't know that calculators had general purpose processors. So what you thought was a condescending post was really the far more favorable post compared to the alternative. 
#612




Quote:
But the question is whether the box is doing "computation". It has been claimed that "computation" could/should be defined as "what a UTM does when it does its thing". So, what to make of a situation where: There is a user (U), a box (B), and a UTM contained within the box. The box only has one button and one light on it. When the button is pressed, the box generates a random program and random data, feeds them into the UTM, and then runs the UTM for up to 10000 cycles. If the UTM halts before then, then the light illuminates. If it doesn't, then the light turns off. So: The box clearly isn't a UTM, because you can't be a UTM unless you have a way to input programs. But the UTM is both clearly a UTM (by definition) and it's clearly behaving in a UTM manner, doing UTM things. If "computation" is a thing UTMs do, then it's definitely doing it. Your argument, though, appears to be that because B isn't a UTM, then nothing within B can be doing computation, because B isn't a UTM. I strongly disagree. The casing you put a processor in doesn't change what the processor is doing. If UTMs do computation when they do what they do, then they do it even if the UTMiness of it all is concealed from all outside users. 
#613




Additional thoughts:
It seems that one of the key point of CTM is that a human brain has the flexibility to learn and execute arbitrary algorithms on symbols. If there is one single function that the human brain can't compute (e.g. 27's in all memory elements) that renders the brain slightly less powerful than a turing complete system, the general point of CTM does not lose value. Under no condition would the human brain have been able to compute all functions anyway, so whether the limitation is due to amount of memory or due to slight weaknesses in a particular instruction set doesn't really change much. 
#614




Quote:
Quote:
First, the condescending "gotcha" that I apparently was not aware of the astounding fact that electronic calculators can be made out of microprocessors is not only condescending but is one of the most remarkable examples of absolutely utter irrelevance I've ever seen. They're made that way today because microprocessors are cheap, handy devices for implementing miscellaneous logical operations; early electronic calculators, of course, were NOT made that way (they were made with discrete transistors and specialpurpose ICs at least until the advent of microprocessors like the Intel 4004 in the early 70s) and before electronic calculators existed, earlier versions were made with mechanical gears. Since they are all equivalent calculators performing exactly the same functions, the mind boggles at what you think the relevance of the microprocessor here is. Not to mention that I've already explained at length  several times  the general case of why the presence of an embedded microprocessor in itself has no bearing on the functional properties of the system in which it's embedded. Second, I have never claimed that the computation performed by one kind of machine is in any way different from the same computation performed by any other kind if they are in fact the same computation. This is an absurd misinterpretation that you keep repeating. The factual assertion is that "computational" in CTM specifically refers to the Turing model of the storedprogram digital computer  not to the nature of any particular computation it performs, but to its ability to execute a sequence of stored instructions on stored data in a completely general way such that it can perform any possible computation (within the limits of its memory and available time). When implemented on digital computers, it refers to the computational capability that is commonly referred to as the von Neumann architecture. Obviously, the substrate of the brain is quite different, but the model is important in illuminating the premise that higher level operations on mental representations are analogous to computer instructions processing symbols, and that cognition emerges from exactly the same kind of computational process. Quote:



#615




It's been great to read this conversation, especially when I had the chance to follow the argumentation of a Higher Self rather than the manifestation of an ego. Thank you everybody for the good moments.

#616




Wait, the thread is over? I had no idea.
Quote:

#617




Quote:
This is the key point you've been missing: capability vs requirement Quote:

#618




Quote:
You may have just been speaking sloppily here, but that's also false: for any nonuniversal TM, a nonTuring complete instruction set is sufficient. Last edited by Half Man Half Wit; 07302019 at 12:00 PM. 
Reply 
Thread Tools  
Display Modes  

