What does the Incompleteness Theorem imply?

[TVAA]

*Originally posted by SentientMeat *
**If I may run in and ask what may be a stupid question like a child interrupting a serious meeting of adults:

In this array of programs, surely at least one of them must be a computer? If they are all programs, nothing would run? Does this show that programs and computers are not equivalent? **

Nope. The programs and computers are just systems of relationships. The behavior of any computer can be seen as the results of a program that describes it, and the behavior of any program can be interpreted as the behavior of a computer.

(What SM doesn’t understand is that a program is just how a particular computer behaves, and a computer is just a set of interactions whose behavior defines a program. He’s getting the program confused with the methods for reconfiguring a device.)

A truly inconsistent program can’t be run; as such, it can’t really be said to exist in the first place, as it’s not actually a program.

[TVAA]

To put this in even simpler terms:

There’s no program without a computer, and there’s no computer without a program.

[Spiritus_Mundi]

Remember all that fuss about whether a “computer” necessarily needs to be able to accept input or generate output? Remember all that fuss about Turing machines that only generated output?

Remeber when I said: a TM is closer in analogy to a program than to a computer. A UTM, then, would be a program that is simulating the behavior of a computer.

A Turing Machine is not a computer. A Turing Machine is an abstract representation of a useful algorithm.

That is why “things Turing Machines can do” are useful for talking about “things useful algorithms can solve”. “Useful” is a descriptive term that summarizes the Church-Turing requirements for an effective mechanical method. Unfortunately, there is no agreed upon formal definition for what constitutes an effective mechanical method, though most people are comfortable working with the concept iuntuitively.

A program, however, is not necessarily an algorithm, though useful programs are both implementations of an algorithm and algorithms themselves. Electronic circuits can also be an implementation of an algorithm. We are dealing with several layers of abstraction, here, and while it is easy to get references between them confused that does not mean that each layer of abstraction is identical.
[ul][li]An algorithm is an abstract method for solving a problem.[/li][li]A Turing machine is an algorithm expressed in a specific abstract form. This form places some restrictions upon the class of algorithms that it can represent (finite states, determinant, at least one input symbol). These restrictions do not prevent Turing machines from modelling any useful algorithms.[/li][li]A Universal Turing Machine is a Turing Machine that can simluate the method encoded in any other Turing Machine.[/li][li]Some people broaden the definition of Universal Turing Machine to include Turing Machines that can simluate some Turing-complete system, but that isn’t the “classical” definition.[/li][li]A Turing-complete system is one that has identical computational power to a Universal Turing Machine.[/li][li]A program is a syntacticly correct series of statements in a particular programming language. Often, though not always, a program performs a “useful” method. In such cases, a program is both an expression of an algorithm and an algorithm itself.[/li][li]There is a one-to-many relationship between algorithms and programs.[/li][li]Expressions of algorithm in physical media (printed circuit, human being, etc.) are not generally considered algorithms, as this strains the meaning of “abstraction”.[/li][li]“Program” can also be used to describe the state of a particular computer, if that computer is expressing an algorithm. That seems to be the way TVAA is using the term. In this sense “program” is not an abstraction (in the usual sense of the word) and is thus not an algorithm either.[/ul][/li]

There’s no program without a computer, and there’s no computer without a program.

No. Each can exist without the other, though they are not particularly useful in their designed tasks.

[DaveW]

TVAA wrote:

But the simulated symbol is an actual symbol.

But it’s not “exactly the same thing.” An ‘A’ on paper is a heck of a lot different from its ASCII representation in bits inside a computer. A program cannot, in fact, “handle” an ‘A’ on paper for input - it must be digitized or otherwise modified in its representation.

But the hardware is the program.

Not at all. The hardware allows the program to interact with the outside world.

An actual computer can’t do anything with input if it doesn’t have a program. (Put another way, the program is whatever the computer does with the input.) The “program” is whatever the internal workings of the computer are set to do.

Great, you’ve just given us your own version of how computers are different from programs.

The devices we use for computation are reconfigurable, which is a large part of what makes them useful. But whenever we “run a program” on the computer, we’re really rearranging the components to produce a new computational system. That’s why ‘computer’ and ‘program’ aren’t formal terms, and why terms like “finite state machine” are used instead. A finite state machine is both computer and program.

Sigh. In the Pit thread, you got upset that Spiritus was using formal terms when you were using informal terms. Now you go ahead and make that switch yourself. Is your point about computers and programs being indistinguishable only valid in the context of formal finite state machines?

It’s not a possibility, it’s a fact.

Okay, then prove that we are all inside a simulation. If it’s a fact, it ought to be verifiable.

If I said that there’s no difference between pie a la mode with ice cream on top of the pie or pie beneath the ice cream, would you say that’s not scientific?

That is something which is determinable through testing. Whether or not we exist solely inside a big simulation is not something that anyone can test. It is scientifically the same as asking if God exists. We cannot probe this question either logically or physically.

Logically, the hardware and the software are equivalent. The only “proof” needed is logical proof.

The disproof then becomes the fact that one piece of hardware cannot ‘execute’ another piece of hardware directly. Hardware and software are not equivalent, or I could surf the Web with nothing but a free AOL CD.

The question then becomes whether the world we see if sufficiently powerful, and it certainly is.

Perhaps based on the logically-flawed premise above, but what about in real life?

We are all thoughts in the mind of God.

Prove it.

To put this in even simpler terms:

There’s no program without a computer, and there’s no computer without a program.

But that doesn’t mean they are “exactly the same thing.”

The fact that the “behavior of any computer can be seen as the results of a program that describes it, and the behavior of any program can be interpreted as the behavior of a computer” (emphasis mine) doesn’t mean that you must interpret things that way. To do so will do nothing but result in confusion when you call tech support for help with your “Microsoft Word Computer” or your “Dell Program.” And show me which state of a TM needs to be fixed when it starts outputting Ls instead of 1s due to a malfunction of the print head.

[Spiritus_Mundi]

Missed this one somehow

A finite state machine is both computer and program.

This is factually incorrect, apart from our philosophical difference of opinion about whether “virtual reality” should be considered a redundancy. A Universal Turing Machine can simlulate the behavior of any computer whose power does not exceed that of a Turing-complete system (a set currently thought to be empty). A generic finite automoata cannot. FA as a class are restricted to only teh computational power of regular languages.

[TVAA]

Incorrect. A finite state machine is both computer and program. The point is that its capacity is limited (hence “finite”). UTMs can indeed do more than any finite state machine… but there is nothing a UTM can do that some finite state machine cannot except emulate another UTM (for obvious reasons).

[TVAA]

*Originally posted by Spiritus Mundi *
**Remeber when I said: a TM is closer in analogy to a program than to a computer. A UTM, then, would be a program that is simulating the behavior of a computer.

A Turing Machine is not a computer. A Turing Machine is an abstract representation of a useful algorithm.
[/quote]
** Incorrect. All computers that exist can be considered special cases of TMs. While to my knowledge no one has ever built a machine matching the description Turing gave as an example, that has nothing to do with whether computers actually are TMs.

A computer is merely the manifested form of an algorithm. If you alter the internal workings of the device, you change the nature of the computer and destroy the algorithm.

**That is why “things Turing Machines can do” are useful for talking about “things useful algorithms can solve”.

** And it’s known that there are some problems which cannot be solved by TMs – like generating all statements that are true in a given system of sufficient complexity…

**A program, however, is not necessarily an algorithm, though useful programs are both implementations of an algorithm and algorithms themselves. Electronic circuits can also be an implementation of an algorithm. We are dealing with several layers of abstraction, here, and while it is easy to get references between them confused that does not mean that each layer of abstraction is identical.

** But each layer is fundamentally the same – it’s just that one layer is somewhat more complex than those ‘above’ it.

[quote]
[li]An algorithm is an abstract method for solving a problem.[/li][/quote]
Incorrect. An algorithm is a series of operations that generates a desired output in a finite number of steps. “Abstract” is a misnomer – or more accurately an ultimately invalid concept.

**A Turing machine is an algorithm expressed in a specific abstract form. This form places some restrictions upon the class of algorithms that it can represent (finite states, determinant, at least one input symbol). These restrictions do not prevent Turing machines from modelling any useful algorithms.

** Incorrect. TMs are “pared down” examples of how algorithms can be carried out. Turing never specified exactly how the operations are actually implemented in TMs… because he never had to. The actual implementation is irrelevant, as there are an infinite number of ways to implement any given set of steps.

[quote]
**[li]A Universal Turing Machine is a Turing Machine that can simluate the method encoded in any other Turing Machine.[/li][/quote]
** Correct. This requires infinite memory space, however, which does not obviously seem to be possible. No UTMs are actually known to exist, although some of their properties have been demonstrated.

[quote]
**[[li]Some people broaden the definition of Universal Turing Machine to include Turing Machines that can simluate some Turing-complete system, but that isn’t the “classical” definition.[/li]
[li]A Turing-complete system is one that has identical computational power to a Universal Turing Machine.[/li][/quote]
** What the “classical” definition is is irrelevant. UTMs can obviously simulate anything that’s Turing complete, since it’s known that any UTM can simulate any other UTM.

[quote]
**[li]A program is a syntacticly correct series of statements in a particular programming language. Often, though not always, a program performs a “useful” method. In such cases, a program is both an expression of an algorithm and an algorithm itself.[/li][li]There is a one-to-many relationship between algorithms and programs.[/li][/quote]
** These statements are correct but incomplete. A program is a specific set of operations that can be carried out by a computer – the way in which they’re described is irrelevant. Statements in computer languages are not themselves algorithms – that’s why compilers were made.

[quote]
**[li]Expressions of algorithm in physical media (printed circuit, human being, etc.) are not generally considered algorithms, as this strains the meaning of “abstraction”.[/li][/quote]
** Invalid reasoning. This may be done in basic, introductory texts to avoid confusion… but the “physical manifestation” is the algorithm: it’s a set of operations (interactions between the elementary components of the system) that can produce results in a finite time. Whether those results are necessarily the desired ones is the question…

[quote]
**[li]“Program” can also be used to describe the state of a particular computer, if that computer is expressing an algorithm. That seems to be the way TVAA is using the term. In this sense “program” is not an abstraction (in the usual sense of the word) and is thus not an algorithm either.[/li][/quote]
** Incorrect.

You seem to have problems with the concept of “abstraction”. A computer that is the result of the workings of another computer is just as ‘real’ as the emulating computer is. This computer exists as a subset of the interactions within the emulating computer. The emulating computer itself is only a subset of an even larger system of interactions, and so forth. Calling one computer “abstract” and the others “concrete” is arbitrary: what we think of as the “physical world” is ultimately just as real and just as illusionary as the simulated ones.

**No. Each can exist without the other, though they are not particularly useful in their designed tasks. **

Incorrect, as you would realize if you thought about the definitions a little more carefully.

[Newton_meter]

*Originally posted by TVAA *
Incorrect.

For someone who doesn’t know what he’s (?) talking about, you sling “incorrect” around an awful lot.

**UTMs can indeed do more than any finite state machine… but there is nothing a UTM can do that some finite state machine cannot except emulate another UTM (for obvious reasons). **

How about recognize the palindromes over the alphabet {0, 1}?

[DaveW]

TVAA wrote:

UTMs can indeed do more than any finite state machine… but there is nothing a UTM can do that some finite state machine cannot except emulate another UTM (for obvious reasons).

This is difficult to parse, to say the least. Let’s see…

“UTMs can indeed do more than any finite state machine…”

Okay, UTMs can do more than FSMs.

“but there is nothing a UTM can do that some finite state machine cannot”

Oops, an FSM can do everything a UTM can do, contrary to the first assertion.

“except emulate another UTM (for obvious reasons).”

Which? UTMs or FSMs? On a first read, it seems obvious that it’s the UTMs which cannot emulate other UTMs, but that’s contrary to the definition of a UTM you agreed to (see below). A UTM which can’t emulate another UTM isn’t very Universal, now is it? And that limitation makes us unable to have a UTM running a UTM running a UTM running a UTM running a TM, which is the sort of situation that “allows” you (you, TVAA) to confuse the computer and the program. Oh, well.

And it’s known that there are some problems which cannot be solved by TMs – like generating all statements that are true in a given system of sufficient complexity…

Seems to me this is true only if the TM is both (A) forced to generate only true statements, and (B) forced to work only within the given system. After all, a TM which is programmed to generate all possible statements in a given system of sufficient complexity will, eventually, generate all the true ones.

[quote]

[li]A Universal Turing Machine is a Turing Machine that can simluate the method encoded in any other Turing Machine.[/li][/quote]
Correct. This requires infinite memory space, however, which does not obviously seem to be possible. No UTMs are actually known to exist, although some of their properties have been demonstrated.

What the heck are you talking about? You’ve been given a link to the state table for a UTM. What is wrong with it that makes it not a UTM, as you are now asserting (which you failed to assert when the link was first presented to you)?

Statements in computer languages are not themselves algorithms – that’s why compilers were made.

If, as you assert, “the representation of a thing is the thing,” then your assertion here is incorrent. Compilers perform a translation from one computer language to another - the thing represented (a description of operations to be performed) is not modified by the compiler, it is simply translated from a (usually) more human-understandable form into a (usually) more computer-understandable form. The steps to be performed do not change. Statements in a computer language are nothing more than a representation of an algorithm, which you assert is that thing: an algorithm. Thus, by your own assertions, you are completely wrong.

And if you’ve never programmed directly in machine code (a computer language requiring no compiler), you’re missing an exorcise in masochism which is, nonetheless, instructive.

what we think of as the “physical world” is ultimately just as real and just as illusionary as the simulated ones.

You can rephrase this assertion all you like, repetition doesn’t make it true. Please provide evidence that this is the case (also provide evidence that we are all just thoughts in the mind of God).

[Spiritus_Mundi]

TVAA: you are wrong about nearly everything you write. [ul][li]No computer is a TM. A TM is an abstraction used to model specific computer behaviors. Computers are actual things that perform calculations and return results.[/li][li]A computer is a device that can run programs. It is not “destroyed” when it runs a different program.[/li][li]Nobody in this thread doubts that there are problems that cannot be solved by TMs. We just doubt the delusional connections you try to draw between GIT and smashing a computer with a hammer.[/li][li]Different layers of abstraction are not “fundamentally” the same except for being “fundamentally” layers of abstraction. [/li][li]The only meaning of complexity that has any relevance for teh behavior of algorithms is one that you have specifically refused to use. YVAA-complexity is of no significance whatsoever to either TMs or GIT.[/li][li]An algorithm is a method. A method is an abstraction. It requires the ability to abstract to connect one action to another in a meaningful series. It requires abstraction to map that set of actions to separate physical circumstances. It requires abstraction to solve a problem in method prior to solving it in practice.[/li][li]You obviously know less about finite state automoata than you do about GIT or Turing Machines, which is frankly an implressive standard of ignorance. An FA is significantly less powerful than a TM. [/li][li]TMs are not “pared down”. Any fully defined TM is an algorithm expressed in a specific language of abstraction. Computer theory provides tools to speak of TMs as a class and thus develop ideas about what properties hold for the general class of “things that solve problems by a finite method”. That does not mean an individual TM is in some sense “pared down” or “unspecified”.[/li][li]You are correct that no UTMs are known to exist, which is one of the more obvious flaws in your arguments that attempt to declare that computers are UTMs.[/li][li]The relevance of the “classical” definition is that it points out that UTM is a label that is not always used consistently. If you are going to build UTMs into your argument, you should specify whether you mean a TM that can simulate any other TM or a TM that can simulate some Turing-complete system. Unless, of course, you suffer from the illusion that there is also no difference between a Turing Machine and a Lambda Calculus. :rolleyes:[/li][li]"UTMs can obviously simulate anything that’s Turing complete, since it’s known that any UTM can simulate any other UTM. " This point is entirely irrelevant to what I wrote. You really should strive to improve your reading skills.[/li][li]Your usage of the terms “program” and “algorithm” are peculiar to TVAA-theory. That’s okay. But your habit of labeling “incorrect” that which does not conform to your idiosyncratic conceptions does nothing but retard an honest exchange of ideas. I have had quite enough of it.[/li]Finally, I have no idea what flight of fantasy impells you to declare abstraction to be an “ultimately invalid concept”, but I don’t really care, either. I had little enough respect for your ideas when there was a chance you might present them in a meaningful form. Since you have now declared abstractions to be ultimately invalid, it resolves all of us from the odious task of trying to sift through your convolutions of nonsense to see if they hide anything of value. After all, what is an idea but an abstraction. Now that I know you feel yours are ultimately invalid I find myself quite happy to agree.[/ul]

[TVAA]

*Originally posted by DaveW *
**TVAA wrote:But it’s not “exactly the same thing.” An ‘A’ on paper is a heck of a lot different from its ASCII representation in bits inside a computer. A program cannot, in fact, “handle” an ‘A’ on paper for input - it must be digitized or otherwise modified in its representation.

** Cannot? Or is it just that the programs you’re familiar with (and that provide the template for your intuitive definition of “program” cannot handle letters on paper.

Besides, you’re confusing the map for the territory. The plastic pieces sitting on a cardboard square don’t carry out computations in chess. They’re just place holders, a memory storage device useful for humans. The pieces themselves exist in human brains… and, in the case of computer chess, exist within the computer. The game itself is entirely virtual.

Determining the concept space defined by the rules of chess is virtually impossible simply because it’s so large. Nevertheless, the rules define all possible valid games. Given an initial starting configuration, it’s theoretically possible to determine if any other configuration of pieces can be reached within a certain number of moves.

The applications of rules and concepts that defines what moves are and are not valid occurs in the players, not the board.

**Not at all. The hardware allows the program to interact with the outside world.

** Not at all. Without the hardware, there is no program. The “program” is merely the configuration of the hardware, a specific possible computer.

**Great, you’ve just given us your own version of how computers are different from programs.

Sigh. In the Pit thread, you got upset that Spiritus was using formal terms when you were using informal terms. Now you go ahead and make that switch yourself. Is your point about computers and programs being indistinguishable only valid in the context of formal finite state machines?

**

I brought up finite state machines not because I wanted to discuss them at length (although I will if I need to), but because you all need to realize why terms like “program” and “computer” aren’t used formally.

Okay, then prove that we are all inside a simulation. If it’s a fact, it ought to be verifiable.

Easy. The world we perceive is one simulated by our brains. Disrupting the function of the brain can disrupt the world we perceive (hallucinations, anyone?).

Furthermore, the world our brain draws on to simulate our experiences is made up of more basic and elemental parts, which is why the “things” that exist in it can be disrupted and destroyed themselves.

If there is a bottom level to reality, it would necessarily not be able to change in any way. The illusion of time wouldn’t hold. This is obviously not that level (well, everything is that level, one way or another).

Ergo…

**That is something which is determinable through testing. Whether or not we exist solely inside a big simulation is not something that anyone can test. It is scientifically the same as asking if God exists. We cannot probe this question either logically or physically.

** Incorrect. Saying that something “exists” puts restraints on its nature. If ‘God’ is defined as an entity that does not have these restraints, we can easily demonstrate logically that God does not exist. If God does exist, then there are ways in which the nature of God’s interactions with the world could be tested scientifically (in theory, if not by our current technology and reach).

**The disproof then becomes the fact that one piece of hardware cannot ‘execute’ another piece of hardware directly. Hardware and software are not equivalent, or I could surf the Web with nothing but a free AOL CD.

** I’m not saying that any piece of ‘hardware’ can act as any piece of ‘software’. I’m saying that conceptually, there’s no difference between hardware considered as a group and software considered as a group.

Given sufficient computer power, it would be possible to generate an accurate model of the CD in sufficient detail so that there’s no meaningful difference between the CD and the simulation. (Although the worlds in which they existed would be somewhat different…)

**The fact that the “behavior of any computer can be seen as the results of a program that describes it, and the behavior of any program can be interpreted as the behavior of a computer” (emphasis mine) doesn’t mean that you must interpret things that way.

** I’m speaking logically, not discussing your possible options. I could choose to describe the behavior of a computer as “vindictive and fluffy cloud candles that defenestrate cromulently”, but that would just be dumb.

**And show me which state of a TM needs to be fixed when it starts outputting Ls instead of 1s due to a malfunction of the print head. **

The program emulating that particular TM has a faulty read-algorithm. I suggest you debug it immediately.

[TVAA]

*Originally posted by Spiritus Mundi *
**No computer is a TM. A TM is an abstraction used to model specific computer behaviors. Computers are actual things that perform calculations and return results.

**

Sorry, Spiritus, but all computers fit within the category of TMs. They read, apply operations, and write. TMs aren’t limited in their methods of doing so.

[quote]
**[li]A computer is a device that can run programs. It is not “destroyed” when it runs a different program.[/li][/quote]
** You’ve claimed that a computer must be able to generate output and accept input, but that a program doesn’t need to be able to. Therefore, a set of instructions can contain an infinite looop and remain a program, but when the program is implemented the device running it is no longer a computer, as it can no longer generate output. An external force would have to intervene, changing the configuration of the device back into making it a computer.

Thus, if we accept your earlier definition (which you cowardly try to back out of now), you prove my OT OP point. If we don’t, and we accept my (correct) statements about the nature of computers and programs, we also prove my point.

Would anyone care to offer another set of definitions?

[quote]
**[li]Nobody in this thread doubts that there are problems that cannot be solved by TMs. We just doubt the delusional connections you try to draw between GIT and smashing a computer with a hammer.[/li][/quote]
** The hammer blow is simply an example of an input the system modelling the “computer” cannot accept while generating results consistent with the “computer”. Logic bombs are examples of somewhat more “abstract” methods of crashing the computer, but they’re all the same in the end: input that cannot be handled.

[quote]
**[li]Different layers of abstraction are not “fundamentally” the same except for being “fundamentally” layers of abstraction. [/li][/quote]
** Incorrect. The principles underlying them all are the same. You’re merely prejudiced towards the ones in which you’re most present; they’re no more real than the others. In fact, there are lots and lots of things “more real” than you are.

[li]The only meaning of complexity that has any relevance for teh behavior of algorithms is one that you have specifically refused to use. YVAA-complexity is of no significance whatsoever to either TMs or GIT.[/li][/quote]
** [sigh] It doesn’t particularly matter to this debate, correct. That’s why I’ve never bothered making it a well-defined concept. It’s just a note in passing.

[quote]
**[li]An algorithm is a method. A method is an abstraction. It requires the ability to abstract to connect one action to another in a meaningful series. It requires abstraction to map that set of actions to separate physical circumstances. It requires abstraction to solve a problem in method prior to solving it in practice.[/li][/quote]
** And that’s precisely what the physical implementation of a concept is. Your brain generates a crude model of the components, determines what will happen when they’re set into a specific configuration, and draws conclusions. If your model preserves the properties of the components, your conclusions will reflect their behavior. Your model is still a real computer.

[li]You obviously know less about finite state automoata than you do about GIT or Turing Machines, which is frankly an implressive standard of ignorance. An FA is significantly less powerful than a TM. [/li][/quote]
** Specific FAs are less powerful than TMs in general. They have to be: they don’t have the same resources. Deny memory to a TM, and you have a finite state machine. On the other hand, grant unlimited memory to a FSM, and what do you get…? TMs!

[quote]
**[li]TMs are not “pared down”. Any fully defined TM is an algorithm expressed in a specific language of abstraction. Computer theory provides tools to speak of TMs as a class and thus develop ideas about what properties hold for the general class of “things that solve problems by a finite method”. That does not mean an individual TM is in some sense “pared down” or “unspecified”.[/li][/quote]
** Not unspecified, more specified. Any individual TM is a specific member of a class referred to as ‘TMs’. It necessarily is more limited than the class is – that’s what makes it an individual member.

[quote]
**[li]You are correct that no UTMs are known to exist, which is one of the more obvious flaws in your arguments that attempt to declare that computers are UTMs.[/li][/quote]
** Not all computers are UTMs, but all UTMs are computers. Your statements about computers and their capabilities were found to be inconsistent with the behavior of UTMs… ergo, your statements were wrong.

[quote]
**[li]The relevance of the “classical” definition is that it points out that UTM is a label that is not always used consistently. If you are going to build UTMs into your argument, you should specify whether you mean a TM that can simulate any other TM or a TM that can simulate some Turing-complete system. Unless, of course, you suffer from the illusion that there is also no difference between a Turing Machine and a Lambda Calculus. :rolleyes:[/li][/quote]
** A TM that can simulate any other TM IS Turing-complete. Duh. “Turing completeness” refers to the ability to simulate any other TM.

Okay, Spiritus, next time I’ll specify whether I’m claiming A or whether I’m merely claiming A. :rolleyes:

Furthermore, once the memory limitations of our computers are ignored, it’s obvious that they are in fact UTMs. Their limited memory puts even more restrictions on what they can do, but anything a UTM can’t do, they can’t do either.

[quote]
[li]"UTMs can obviously simulate anything that’s Turing complete, since it’s known that any UTM can simulate any other UTM. "** This point is entirely irrelevant to what I wrote. You really should strive to improve your reading skills.[/li][/quote]
** You should really do a better job of misrepresenting what you say. If you need to, take a look at the quoted section immediately before this one and think more carefully about what you type next time.

[quote]
**[li]Your usage of the terms “program” and “algorithm” are peculiar to TVAA-theory. That’s okay. But your habit of labeling “incorrect” that which does not conform to your idiosyncratic conceptions does nothing but retard an honest exchange of ideas. I have had quite enough of it.[/li][/quote]
** My usage is perfectly consistent the with the general definitions. I’m simply carrying those definitions out to their logical conclusions, while you tarry about with superficial impressions and ignore the deeper implications.

[quote]
**[li]Finally, I have no idea what flight of fantasy impells you to declare abstraction to be an “ultimately invalid concept”, but I don’t really care, either. I had little enough respect for your ideas when there was a chance you might present them in a meaningful form. Since you have now declared abstractions to be ultimately invalid, it resolves all of us from the odious task of trying to sift through your convolutions of nonsense to see if they hide anything of value. After all, what is an idea but an abstraction. Now that I know you feel yours are ultimately invalid I find myself quite happy to agree.[/list] **[/li][/QUOTE]
Abstractions, as considered separately from reality, have no meaning. No such abstraction exists. Abstractions are a word we use to describe certain properties of physical systems.

There isn’t any difference between “abstractions” and “realities”. Deal with it.

[TVAA]

*Originally posted by DaveW *
**This is difficult to parse, to say the least. Let’s see…

“UTMs can indeed do more than any finite state machine…”

Okay, UTMs can do more than FSMs.

“but there is nothing a UTM can do that some finite state machine cannot” “except emulate another UTM (for obvious reasons).”

Oops, an FSM can do everything a UTM can do, contrary to the first assertion.

**

There are no functions that a UTM can perform that some FSM cannot perform, excepting only simulating things with infinite memory (which FSMs can’t do by definition). Any UTM can do things that some specific FSM can’t do, but not things all FSMs can’t do (exception previously discussed). We can always imagine a FSM sufficiently powerful enough to handle any problem solvable in a finite number of steps.

**Which? UTMs or FSMs? On a first read, it seems obvious that it’s the UTMs which cannot emulate other UTMs, but that’s contrary to the definition of a UTM you agreed to (see below). A UTM which can’t emulate another UTM isn’t very Universal, now is it? And that limitation makes us unable to have a UTM running a UTM running a UTM running a UTM running a TM, which is the sort of situation that “allows” you (you, TVAA) to confuse the computer and the program. Oh, well.

** UTMs can emulate other UTMs. “Not being able to emulate UTMs” is the property FSMs necessarily have.

And it’s not a confusion. It’s truth.

**Seems to me this is true only if the TM is both (A) forced to generate only true statements, and (B) forced to work only within the given system. After all, a TM which is programmed to generate all possible statements in a given system of sufficient complexity will, eventually, generate all the true ones.

** But that’s not possible in finite time. Systems of infinite complexity contain an infinite number of theorems.

And you’re missing the point. Is a statement “possible” when it would be allowed by the grammatical rules of the system, or is it “possible” when it can be generated from initial states according to the operations of the system?

GIT shows that, for any sufficiently powerful system, there are perfectly well-formed statements (not grammatically incorrect) that cannot be derived from the initial axioms. If the rules the TM are using to generate statements simply generate all possible statements, those rules aren’t powerful enough. (The rules describing how the TM functions still are, though. )

**Correct. This requires infinite memory space, however, which does not obviously seem to be possible. No UTMs are actually known to exist, although some of their properties have been demonstrated.

What the heck are you talking about? You’ve been given a link to the state table for a UTM. What is wrong with it that makes it not a UTM, as you are now asserting (which you failed to assert when the link was first presented to you)?
[/quote]
** A UTM needs infinite memory space. If it had infinite memory, I can easily accept that it would be a UTM.

The computers we’re typing on would be UTMs if they had enough memory.

Didn’t you read that part of my statement about “infinite memory”?

**If, as you assert, “the representation of a thing is the thing,” then your assertion here is incorrent. Compilers perform a translation from one computer language to another - the thing represented (a description of operations to be performed) is not modified by the compiler, it is simply translated from a (usually) more human-understandable form into a (usually) more computer-understandable form. The steps to be performed do not change. Statements in a computer language are nothing more than a representation of an algorithm, which you assert is that thing: an algorithm. Thus, by your own assertions, you are completely wrong.

** I’m afraid I don’t follow. It doesn’t matter how the statements are written down or stored – they have no significance that way. If you destroy all of the systems that link certain symbols with manifestations of concepts, you destroy the meaning of those symbols.

**And if you’ve never programmed directly in machine code (a computer language requiring no compiler), you’re missing an exorcise in masochism which is, nonetheless, instructive.

** What lesson does it teach that you believe I need to learn?

**You can rephrase this assertion all you like, repetition doesn’t make it true. Please provide evidence that this is the case (also provide evidence that we are all just thoughts in the mind of God). **

Ever hear of the medieval Christian sect that believed that the world had already ended and that the universe was merely the memory of God?

Do you know what the problem with their theological system was?

What’s the difference between the memory of an omniscient God and an “external and independent” world created by an omnipotent God?

[Spiritus_Mundi]

Premise: TVAA is ignorant of what Turing_complete means, despite the fact that it has been defined in this thread.

**Spiritus: **A Turing-complete system is one that has identical computational power to a Universal Turing Machine.

**TVAA: **“Turing completeness” refers to the ability to simulate any other TM.

Q.E.D.

Premise: TVAA distorts his own language so casually that he cannot be trusted with even the simplest exchange of information.

**TVAA: **there is nothing a UTM can do that some finite state machine cannot except emulate another UTM (for obvious reasons).

**Spiritus: **You obviously know less about finite state automoata than you do about GIT or Turing Machines, which is frankly an implressive standard of ignorance. An FA is significantly less powerful than a TM.

**TVAA: **Specific FAs are less powerful than TMs in general. They have to be: they don’t have the same resources. Deny memory to a TM, and you have a finite state machine.

**TVAA: **There are no functions that a UTM can perform that some FSM cannot perform, excepting only simulating things with infinite memory . . . We can always imagine a FSM sufficiently powerful enough to handle any problem solvable in a finite number of steps.

**Q.E.D. **

(Though one might have to know a little bit about FSM to recognize it. Note that TVAA hedges his bets by sloppily going back and forth in terminology. He uses FSM in some statements and FA in others. What is important to know is that FSM as a generic description is a category that includes: Finite Automata, Mealy Machines, Moore Machines, Turing Machines, etc. So if TVAA means the generic class, then there is absolutely no distinction between what an FSM can do and what a TM can do. FSM is also sometimes used interchangealy with FA. In that case TVAA is also wrong, since FA are restricted to accepting only regular languages while a TM can accept recursively enumerated languages.)

Premise: TVAA uses words in contradictory manners and then hides behind the illusion that he is simply relying upon “common” definitions. This is, of course, not the tactic of an honest man.

“TMs are “pared down” examples of how algorithms can be carried out. Turing never specified exactly how the operations are actually implemented in TMs… because he never had to.”

“all computers fit within the category of TMs.”

So, TMs are “unspecified” about how they perform poperations but every computer is a TM. :rolleyes: And, of course, we have the lovely:

My usage is perfectly consistent the with the general definitions. I’m simply carrying those definitions out to their logical conclusions

[ul][li]There isn’t any difference between “abstractions” and “realities”. [/li][li]I’m saying that conceptually, there’s no difference between hardware considered as a group and software considered as a group.[/li][li]Without the hardware, there is no program. The “program” is merely the configuration of the hardware, a specific possible computer.[/li][/ul]

Q.E.D.

Premise: TVAA “reasons” in a style of pop-metaphysical bullshit that is both self-contradictory and absurd.

“the representation of a thing is the thing”

“you’re confusing the map for the territory.”

“each layer is fundamentally the same – it’s just that one layer is somewhat more complex than those ‘above’ it.”

"If there is a bottom level to reality, it would necessarily not be able to change in any way. "

“The principles underlying them all are the same. You’re merely prejudiced towards the ones in which you’re most present; they’re no more real than the others. In fact, there are lots and lots of things “more real” than you are.”

Q.E.D.

Premise: TVAA reads too poorly to hope for a productive written exchange of ideas.

**Spitirus: **Some people broaden the definition of Universal Turing Machine to include Turing Machines that can simluate some Turing-complete system, but that isn’t the “classical” definition.

**TVAA: **UTMs can obviously simulate anything that’s Turing complete, since it’s known that any UTM can simulate any other UTM.

**Spitirus: **This point is entirely irrelevant to what I wrote. You really should strive to improve your reading skills.

**TVAA: **You should really do a better job of misrepresenting what you say. If you need to, take a look at the quoted section immediately before this one and think more carefully about what you type next time.

If I need to? :wally You need to think more carefully. Period.

Q.E.D.

Conclusion: Bye.

[erislover]

“you’re confusing the map for the territory.”

“each layer is fundamentally the same – it’s just that one layer is somewhat more complex than those ‘above’ it.”

LOL