Printable View
Does anybody know what is the simplest possible theoretical programming language that is capable of doing all computing tasks? I assume it to be a language with just the following two instructions and the ability to create variables (eg a, b, c ... ) but maybe that is optimistic:
Let a = b
if a < b then go to instruction x
I assume Turing had a lot to say on this subject ...
I have a good reason for asking this which I would rather not go into at this point. All help greatly appreciated!
Here is a very simple Turing-complete language.
Yes, binary and XOR.Quote:
Does anybody know what is the simplest possible theoretical programming language that is capable of doing all computing tasks?
The answer's flippant, of course, but only because the question doesn't really make sense. What do you mean by "programming language" and what do you mean by "All Computing Tasks"?
It makes perfect sense. He means Turing Complete languages. For simplicity sake, lets call a Turing Complete language any language which in theory, you can write Word in. He is asking for the simplest one. My first post shows the simplest one I know. Although its a language made for the amusement of programmers, you could theoretically write MS Word in it if you had a few hundred years to spare.Quote:
Originally Posted by FunkyDexter
I don't know whether it counts, but take a look at the instruction set of a RISC architecture chip. The ASM for such a processor is probably about as simple as you can get.
EDIT: I see that I was hooked on practicality. You can get simpler if you want it to be useless.
Practicality is not what he is asking about but qualification as a capable language. Turing Completeness is the concept used to determine that. It doesn't matter how simple or impractical a language is, if it can perform all the basic math operations, do conditional branching and reference discrete blocks of memory, it can be used to write any program. I'm willing to be the instruction set for RISC can do all these things which means it would be able to run any program your normal PC can run if given enough memory. It may not run pretty but it will run.
Precisely, thank you!Quote:
Originally Posted by Niya
Hmm...I may have been wrong in that Brain**** is the simplest. OISC seems to be the simplest Turing Complete system ever devised. This system has only a single instruction that behaves differently according to the data that the instruction operates on. The Wikipedia article doesn't really make it clear weather any such CPU has actually been built or if its only still on paper, but they do attempt to explain how it can be used to implement any algorithm.
That's not a language at all, though, it's a CPU with a single instruction in the instruction set. The language would be the sequence of inputs that produced a certain output. Similarly, the instruction set on an x86 is not a language. A language is a series of those instructions in sequence.
Ok good point but what I'm getting at is that its capable of implementing algorithms written in Turing Complete languages like C or VB.Quote:
Originally Posted by Shaggy Hiker
True, but that just means that it is a processor capable of hosting a modern OS....though I can't seem to shake the image of a pyramid balanced on its tip.
Ummm...hmm. I don't think you're getting it......Ok how about this. Lets consider anything, from XAML to every imperative, object-oriented and functional programming language to be a language. Include descriptive languages like XAML, HTML, CSS. Lets also include instruction sets and byte-code instruction sets like MSIL. Now what he is asking is which one of these languages is the simplest yet still capable of performing computations of such complexity that the language itself can be computationally universal. To use your example of an OS....can the language or system describe something as complicated as an OS ? It need not be that complicated though. If you can write, say a calculator in it then it can be considered Turing Complete.
Please note that its not so much about practicality as it is possibility. The question is can the language or instruction set describe the implementation. It is possible to describe a calculator implementation in brain**** but you can't do so in say, HTML. HTML lacks anything to describe operations like addition and subtraction, it has no concept that could facilitate the description of a loop hence HTML is not a Turing Complete system.
[EDIT]
One other thing...The basic needs don't have to be directly implemented. Loops are necessary to implement some algorithms but a language or instruction set with a GOTO or its ilk like a jump instruction can be used to implement algorithms that need loops to implement. Even a high level language with no Do...Loop/For...Next can implement such algorithms if it can perform recursive calls.
Another example....Imagine a language without a multiplication operator. If it has an addition operator and looping, then you can implement multiplication which means you can implement any algorithm that requires multiplication.
After thinking about it, I guess that OISC technically is a language, despite the fact that it wouldn't be useable. Machine code is a language, too, but nobody in their right mind writes in that, nor would they in OISC. However, it does fit the criteria, so it technically complies.
That's kinda where I stood with the whole binary and XOR thing. XOR operators can be combined to form every other logical operation. Combine them with binary and you can ultimately produce solve any mathematical problem. So, in turn, you can theoretically produce any program, no matter how complicated. The only bit I missed would be the ability to "reference discrete blocks of memory" and I'm actually not sure that's necessary to solve a complex problem, it just makes it a lot easier (and if it really is necessary I only require the addiotion of a pen and paper).
Of course, I'm being pretty focetious but only to highlight how diffictult it is to define the term "programming language" (well, that and a cheap shot to make myself look clever... well, we are in ChitChat after all:p) and as an example a quick google for the phrase "Turing Complete" turns up this definition on StackOverflow:-
Once again, I refer you to my binary and XOR suggestion... which meets those criteria. I don't imagine for a second that anyone would seriously consider binary and XOR to be "Turing Complete" but you can't actually argue it isn't based on the definitions available.Quote:
A Turing Complete system means a system in which a program can be written that will find an answer (although with no guarantees regarding runtime or memory).
So, if somebody says "my new thing is Turing Complete" that means in principle (although often not in practice) it could be used to solve any computation problem.
It is necessary. If you look at it closely, you'd realize that memory is actually just a way to preserve a state. The more memory you have, the more states your system has. You can then use your instruction set to act on these states. Imaging a system that can only be in one of two states at a time. Another way to put it would be to say that the system has one bit of memory. If I gave you a stack, an Add instruction to go with that system and asked you to produce and algorithm that take two inputs, adds them and produce a results, you'd quickly realize its impossible. You cannot even represent inputs, there is only room for the system's current state. Bearing that in mind, if a language doesn't allow you to perform operations on, read or change the state of the system, then you are prevented from implementing certain algorithms. Think of old static HTML. The system itself(the rendering engine) can be in many states and while HTML does allow you to manipulate the state of the system, it doesn't have a way to reference the state, there for you cannot use them to perform any operations. This is why the ability to reference memory is an important criteria for universal computation.Quote:
Originally Posted by FunkyDexter
If you had a language with only XOR as an operation and the semantics of the language allowed you to simulate any operation on a Turing Complete system then your language must also be Turing Complete.Quote:
Once again, I refer you to my binary and XOR suggestion... which meets those criteria. I don't imagine for a second that anyone would seriously consider binary and XOR to be "Turing Complete" but you can't actually argue it isn't based on the definitions available.
[sarcastic]Wow, you don't say[/sarcastic]:rolleyes:Quote:
you'd realize that memory is actually just a way to preserve a state
Look again at the definition of "Turing Complete" I found. Does it mention anywhere an ability to manipulate or store state? Nope, it only mentions the ability to solve any computational problem. State isn't necessary for that. 1+1=10... no need for state there at all. And that's my point, until you tightly define what you mean by "programming language" then discussions about which is the theoretically simplest are moot. And tightly defining what is meant by "programming language" is an almost impossible task.
:ehh:Quote:
Originally Posted by FunkyDexter
I thought you'd bi into my mathematical aproach but I guess there was nary a chance of that.
It was just a little bit confusing.
it would be wise to shift into a different mental gear if you really wanted to understand it.
Well, that answers a bit shifty, I'd say.
And the insanity starts :eek:
I think this is pretty close...
http://hackaday.com/2013/03/21/nandp...mostly-wiring/
One instruction only. It's simple... not easy. There's a difference. :)
That is wonderfully, insanely cool :)