Unary Processor

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Unary Processor

Postby quintopia » Wed Sep 01, 2010 8:33 pm UTC

Image

Since a computer program, when converted to machine code, is just a very large binary number, it is not implausible (only silly) to encode in unary, with only an exponential blowup in the length of the program! (In a world where this was a common thing to do, backtracking search for TSP would be positively efficient in terms of the length of the input, but that's beside the point.)

I was thinking about what sorts of things would work in order to create a unary processor. What I concluded was this: since all symbols in the string are the same, there is no chance of any localized information in a program.

Thesis: There is no physically implementable computing device that satisfies all of the following:
-Given enough time and memory, it can run any program that computes any computable function
-All programs are stored in unary
-The device does useful work on the problem being solved as the program is being loaded from memory. In particular, it does anything at all before the entire program has been read.

Can someone suggest a way to express and prove this formally?

Laguana
Posts: 49
Joined: Sat Jan 19, 2008 10:13 pm UTC

Re: Unary Processor

Postby Laguana » Thu Sep 02, 2010 1:03 am UTC

I want to say that this is the same as a Turing machine with a 1 symbol alphabet (And a blank), so your proof could be something along the lines of showing that such a machine cannot simulate a Turing machine with a 2 symbol(+blank) alphabet (to show that 1 and 2 cannot hold together).

However, if you are tricky with the blanks this might not be the case (encoding a sequence of numbers like n1 B n2 B n3 B n4 BB). In a situation where "everything is encoded in unary" there is the concept of "the thing" and "not the thing", and you need the latter to know where the unary string ends, but if you can manipulate it then you get back to binary somewhat. If blanks are disallowed within the unary string, then I think the above will hold.

Alternately, as far as showing that 2 and 3 can't work together (depending on what you mean by "anything at all"; it could remove a finite number of digits and remember that, but that is somewhat trivial), a counting argument might work out? If it did something after k symbols in a string of length m1>k, it would do the same thing (for a deterministic machine) after k symbols in a string of length m2>k, so it is limited in what it can distinguish.

User avatar
Xanthir
My HERO!!!
Posts: 5410
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Unary Processor

Postby Xanthir » Thu Sep 02, 2010 4:05 am UTC

Laguana wrote:I want to say that this is the same as a Turing machine with a 1 symbol alphabet (And a blank), so your proof could be something along the lines of showing that such a machine cannot simulate a Turing machine with a 2 symbol(+blank) alphabet (to show that 1 and 2 cannot hold together).

However, if you are tricky with the blanks this might not be the case (encoding a sequence of numbers like n1 B n2 B n3 B n4 BB). In a situation where "everything is encoded in unary" there is the concept of "the thing" and "not the thing", and you need the latter to know where the unary string ends, but if you can manipulate it then you get back to binary somewhat. If blanks are disallowed within the unary string, then I think the above will hold.


Blanks aren't allowed. To encode a program in unary, you just take the program in ordinary binary, interpret it as a binary number, then write that in unary. (There are other ways to possibly write it, but they're functionally equivalent to this.)
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

++$_
Mo' Money
Posts: 2370
Joined: Thu Nov 01, 2007 4:06 am UTC

Re: Unary Processor

Postby ++$_ » Thu Sep 02, 2010 4:46 am UTC

It seems like you'd have to show that given any number [imath]n[/imath] and any set [imath]S[/imath] of instructions, there's a program [imath]N > n[/imath] such that running [imath]N[/imath] requires performing a sequence of instructions disjoint from [imath]S[/imath].

That would mean that if you get to [imath]n[/imath], you couldn't execute any particular set of instructions, because you could be reading the program [imath]N[/imath], which requires you to run a completely different set of instructions.

Of course, you could guess at some of the instructions you might need to run. For example, it might be really common (or at least, not infinitely uncommon) for the first step to be copying the value from R1 into the accumulator; in that case, you should copy the value from R1 into the accumulator before the program is loaded, and then throw the result away if it turns out not to be a useful step. That doesn't seem like it counts, though.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Unary Processor

Postby quintopia » Thu Sep 02, 2010 4:52 am UTC

Let's just assume that yes, there is an EOF/BOF character, and that reading said character is the only way to find where the program ends and begins, and thereby determine its length.

The problem I've been having is formalizing the idea of fetching the program, without specifying anything about the order in which it is fetched. But formalizing the idea of program-boundary-markers makes this really obvious; there are only two pieces of information to determine: where the program begins and where it ends. Assuming we are given one of these in order to locate the program at all, then there is really only one way to read the program: Find the other boundary.

Now, if we assume that there may be other programs in memory, then the only way we can be sure that the boundary we found is the boundary of THIS program is via a sequential search. Any search that involves skipping ahead has a chance of skipping over the boundary and finding a different program's boundary instead. At this point, we can apply Laguana's indistinguishability argument and we are done.

However, there's another type of machine for which this argument doesn't work: Imagine that each program in memory uses a different symbol as its one instruction. Now, it is possible to use more complicated search procedures to find the other boundary, since you can tell by the symbol you are looking at whether you have gone too far. In this machine, it is possible to do meaningful work before the entire program has been read.

Let the boundary search algorithm be as such: Double the distance skipped ahead looking for the boundary at each step until the boundary of your program has been passed. At this point, begin a binary search for the boundary between the last checked position and the current position. Every time you eliminate the "left" half of the search space, interpret it as a 1, and every time you eliminate the "right" half interpret it as a zero. Every 3 bits acquired, execute the BF instruction encoded by this number. By this algorithm, as soon as the end of the program is reached, execution has completed, so we achieve condition 3. Since BF is Turing-complete, we achieve condition 1. And since every program in memory is encoded via a single (albeit distinct) symbol, we achieve condition 2.

cogman
Posts: 112
Joined: Sun May 18, 2008 2:17 pm UTC

Re: Unary Processor

Postby cogman » Thu Sep 02, 2010 2:42 pm UTC

I'm sorry, but WHAT? You CAN'T have a unary computer that does anything. Ever every single symbol is the same, you end up with a system that has no way of telling what is going on. The moment you introduce any sort of method to distinguish one instruction from another, you have created a binary system (with distinguisher and the other symbols being 1s and 0s). A unary system that does any computation just can not exist as it will only have one state (on).

Notch
Posts: 318
Joined: Tue Dec 12, 2006 5:52 pm UTC
Location: Stockholm, Sweden
Contact:

Re: Unary Processor

Postby Notch » Thu Sep 02, 2010 3:29 pm UTC

cogman wrote:I'm sorry, but WHAT? You CAN'T have a unary computer that does anything. Ever every single symbol is the same, you end up with a system that has no way of telling what is going on. The moment you introduce any sort of method to distinguish one instruction from another, you have created a binary system (with distinguisher and the other symbols being 1s and 0s). A unary system that does any computation just can not exist as it will only have one state (on).


It really depends on your definition of a unary computer. If the memory is a fixed pool of 0's, then it won't do anything no as there's just a single state in the machine. But if the memory and registers were to be, say, piles of eggs (unary), then you can suddenly do anything at all.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Unary Processor

Postby quintopia » Thu Sep 02, 2010 4:09 pm UTC

Exactly. The identifying feature of a unary system that I'm paying attention to is not that only a single symbol is available period, but more that all of the functionality of a program is encoded in a single parameter: its size/length.

Axidos
Posts: 167
Joined: Tue Jan 20, 2009 12:02 pm UTC
Location: trapped in a profile factory please send help

Re: Unary Processor

Postby Axidos » Thu Sep 02, 2010 4:51 pm UTC

I'm not convinced that actually satisfies a unary computer.

In unary, you have one state (on) as cogman said. This means you have one piece of information to work with: 1. Quintopia, you said: "Let's assume that there is an EOF or BOF character." I will assume that. In order to recognise the EOF/BOF character, it must be different from all other characters, which are all 1. However, for it to be something other than a 1 means you no longer have only 1s and you are no longer a unary computer. Therefore, the EOF/BOF must be exactly like all other output and as a result don't actually exist.
Note that having a program run out at some point also introduces another state (off/0).

As for the eggs analogy, to say the piles of eggs are significant is to introduce new states. In unary you only have: egg. In binary, you get: egg or not-egg. To have piles of eggs and make their arrangement significant requires, at the very least, distance (or else all existence resides at a single point which all eggs simultaneously occupy, which makes arranging them in stacks quite the nontrivial matter). Since distance requires no-egg to be distinguished, it is already binary. If you do not have not-egg, you just have endless indistinguishable egg forever in all directions. This is pretty much identical to the EOF/BOF character issue at this point.

User avatar
Xanthir
My HERO!!!
Posts: 5410
Joined: Tue Feb 20, 2007 12:49 am UTC
Location: The Googleplex
Contact:

Re: Unary Processor

Postby Xanthir » Thu Sep 02, 2010 5:48 pm UTC

Axidos wrote:I'm not convinced that actually satisfies a unary computer.

In unary, you have one state (on) as cogman said. This means you have one piece of information to work with: 1. Quintopia, you said: "Let's assume that there is an EOF or BOF character." I will assume that. In order to recognise the EOF/BOF character, it must be different from all other characters, which are all 1. However, for it to be something other than a 1 means you no longer have only 1s and you are no longer a unary computer. Therefore, the EOF/BOF must be exactly like all other output and as a result don't actually exist.
Note that having a program run out at some point also introduces another state (off/0).

As for the eggs analogy, to say the piles of eggs are significant is to introduce new states. In unary you only have: egg. In binary, you get: egg or not-egg. To have piles of eggs and make their arrangement significant requires, at the very least, distance (or else all existence resides at a single point which all eggs simultaneously occupy, which makes arranging them in stacks quite the nontrivial matter). Since distance requires no-egg to be distinguished, it is already binary. If you do not have not-egg, you just have endless indistinguishable egg forever in all directions. This is pretty much identical to the EOF/BOF character issue at this point.

You seem to be slightly confused.

Saying "III + IIII = IIIIIII" is unary math. There are separating things of not-I, but it's still unary because each digit is worth the same value.

The identifying aspect of an unary computer would be that as many things as possible are undifferentiated bags of eggs. So, for example, individual programs would be unary numbers.
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

cogman
Posts: 112
Joined: Sun May 18, 2008 2:17 pm UTC

Re: Unary Processor

Postby cogman » Thu Sep 02, 2010 6:04 pm UTC

Xanthir wrote:
Axidos wrote:I'm not convinced that actually satisfies a unary computer.

In unary, you have one state (on) as cogman said. This means you have one piece of information to work with: 1. Quintopia, you said: "Let's assume that there is an EOF or BOF character." I will assume that. In order to recognise the EOF/BOF character, it must be different from all other characters, which are all 1. However, for it to be something other than a 1 means you no longer have only 1s and you are no longer a unary computer. Therefore, the EOF/BOF must be exactly like all other output and as a result don't actually exist.
Note that having a program run out at some point also introduces another state (off/0).

As for the eggs analogy, to say the piles of eggs are significant is to introduce new states. In unary you only have: egg. In binary, you get: egg or not-egg. To have piles of eggs and make their arrangement significant requires, at the very least, distance (or else all existence resides at a single point which all eggs simultaneously occupy, which makes arranging them in stacks quite the nontrivial matter). Since distance requires no-egg to be distinguished, it is already binary. If you do not have not-egg, you just have endless indistinguishable egg forever in all directions. This is pretty much identical to the EOF/BOF character issue at this point.

You seem to be slightly confused.

Saying "III + IIII = IIIIIII" is unary math. There are separating things of not-I, but it's still unary because each digit is worth the same value.

The identifying aspect of an unary computer would be that as many things as possible are undifferentiated bags of eggs. So, for example, individual programs would be unary numbers.

and how do you differentiate between III + IIII and IIIIII + III. How do you let the system know "Hey, we are doing this." Even just counting implies that there is some sort of identifier that signals that no more things exists (the non presence of something is datam).

Notch
Posts: 318
Joined: Tue Dec 12, 2006 5:52 pm UTC
Location: Stockholm, Sweden
Contact:

Re: Unary Processor

Postby Notch » Thu Sep 02, 2010 6:06 pm UTC

Argh, now I got stuck trying to implement Rule 110 (which is turing complete) in a unary computer that can only add and remove a single egg at a time from a pile, and the only test is whether the pile is empty or not.

Notch
Posts: 318
Joined: Tue Dec 12, 2006 5:52 pm UTC
Location: Stockholm, Sweden
Contact:

Re: Unary Processor

Postby Notch » Thu Sep 02, 2010 6:16 pm UTC

cogman wrote:how do you differentiate between III + IIII and IIIIII + III. How do you let the system know "Hey, we are doing this." Even just counting implies that there is some sort of identifier that signals that no more things exists (the non presence of something is datam).


[edit]
Removed stupid analogy! :D
[/edit]

You don't need counting!
I'm fairly sure just being able to add or remove single eggs and testing for empty piles is enough to do anything. A hardcoded system that does just those things but implements something else that's turing complete and programmable would prove that the system is turing complete and programmable.

For example, using some kind of fake unary c-like language, here are a few useful methods:

Code: Select all

clear(Pile a) {
  while (a.notEmpty()) a.removeEgg();
}

copy(Pile from, Pile to) {
  Pile scratch;
  clear(to);
  while (from.notEmpty()) {
    from.removeEgg();
    to.addEgg();
    scratch.addEgg();
  }
  while (scratch.notEmpty()) {
    scratch.removeEgg();
    from.addEgg();
  }
}

mul(Pile a, Pile b, Pile result){
  Pile scratch;
  while (a.notEmpty()) {
    a.removeEgg();
    copy(b, scratch);
    while (scratch.notEmpty()) {
      scratch.removeEgg();
      result.addEgg();
    }
  }
}

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Unary Processor

Postby WarDaft » Thu Sep 02, 2010 6:38 pm UTC

1) Start with n = 1
2) Compute n.
3) Check if there is another 1, if so, n++; goto 2, else halt.

The computer will, in every case, compute the program in question before it has finished reading from input.


As for an actual unary computer, there is no feasible way to make one with only one symbol at the hardware level. However, we can emulate a system in which there is a single register which can be incremented and decremented, and will tell us if we try to decrement 0. Where we go from there determines the power of the system. I am not sure if a pushdown automaton with a single register is TC.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Unary Processor

Postby Yakk » Thu Sep 02, 2010 7:31 pm UTC

Run-while-loading unary Turing computer:

Code: Select all

int current = 0;
do {
  simulate 2^size steps of all programs of value current+1.  Cache the results.
  read a unary bit
  increment current.
  if we have read every unary bit, use the above Cache, then continue simulating until we are done. 
} until done

Given a sufficiently expensive "read a unary bit" operation, the above could be efficient. One could imagine doing the read during the simulations instead of sequentially as well.

A more advanced version would do it in parallel, and be willing to pass current+1. As bits are read in, it would discard low value programs.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

userxp
Posts: 436
Joined: Thu Jul 09, 2009 12:40 pm UTC

Re: Unary Processor

Postby userxp » Fri Sep 03, 2010 1:07 pm UTC

Wouldn't that be a Counter Machine?
A counter machine comprises a set of one or more unbounded registers, each of which can hold a single non-negative integer, and a list of (usually sequential) arithmetic and control instructions for the machine to follow.

Any unary memory can be interpreted as a register. You just need a way to implement the instructions.
You could just have a register for each instruction :P .

User avatar
Sizik
Posts: 1251
Joined: Wed Aug 27, 2008 3:48 am UTC

Re: Unary Processor

Postby Sizik » Fri Sep 03, 2010 11:34 pm UTC

Notch wrote:You don't need counting!
I'm fairly sure just being able to add or remove single eggs and testing for empty piles is enough to do anything. A hardcoded system that does just those things but implements something else that's turing complete and programmable would prove that the system is turing complete and programmable.


Wait, would brainfuck count?
she/they
gmalivuk wrote:
King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.

Notch
Posts: 318
Joined: Tue Dec 12, 2006 5:52 pm UTC
Location: Stockholm, Sweden
Contact:

Re: Unary Processor

Postby Notch » Sat Sep 04, 2010 1:01 am UTC

Yes. Or Game of Life, or Minesweeper.

Axidos
Posts: 167
Joined: Tue Jan 20, 2009 12:02 pm UTC
Location: trapped in a profile factory please send help

Re: Unary Processor

Postby Axidos » Sat Sep 04, 2010 9:17 am UTC

Okay, here's the thing that's bugging me about this whole concept:

In a binary machine you can transmit signals (e.g. LAN, or to the processor) in the form of 0s and 1s. Does no signal count as a third state, or as 0?

If it counts as 0, then binary machines are considered to be endlessly receiving binary signals (so it's endlessly receiving either 0s or 1s) so unary processors would receive an unceasing uniform signal which is useless.

If it counts as a third state, then unary machines may be feasible since they can operate with 1s or no-signal and therefore distinguish length of signals and differentiate commands. I don't think it does count as a third state though: binary computers operate on a basis of charge (1) or no charge (0), right? No signal is no charge, or 0.

The length-based unary processor we're talking about could just be a very convoluted approach to a binary processor. Either that or it's precisely this convoluted approach that means it's a unary processor - but it's still using binary very directly, and that bugs me. Maybe I just don't get it.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Unary Processor

Postby quintopia » Sat Sep 04, 2010 10:49 pm UTC

The question here wasn't whether unary machines are feasible. That I was taking for granted. The question was whether a unary machine could do useful work before the entire program was read.

Yakk has also suggested a good way this could be done. Thanks, Yakk. I can always count on you to answer the question at hand. :wink:

EDIT: One minor adjustment, though, "all programs of size current+1" should be "the program of size current+1" since, in unary, there can be only one program of any given length...

User avatar
Thesh
Made to Fuck Dinosaurs
Posts: 6579
Joined: Tue Jan 12, 2010 1:55 am UTC
Location: Colorado

Re: Unary Processor

Postby Thesh » Sat Sep 04, 2010 11:14 pm UTC

quintopia wrote:The question here wasn't whether unary machines are feasible. That I was taking for granted. The question was whether a unary machine could do useful work before the entire program was read.

Yakk has also suggested a good way this could be done. Thanks, Yakk. I can always count on you to answer the question at hand. :wink:

EDIT: One minor adjustment, though, "all programs of size current+1" should be "the program of size current+1" since, in unary, there can be only one program of any given length...


No, it would not be possible to anything useful unless the entire program was read. If it was, then every single program would essentially contain every program before it. It would basically need to be a random instruction generator based on a numeric seed.
Summum ius, summa iniuria.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Unary Processor

Postby quintopia » Sun Sep 05, 2010 12:46 am UTC

Thesh: you are conveying my intuition on the subject also. I'm unsatisfied with my solution above, and with Yakk's, now that I think about it. They seem to cheat in some subtle way that ignores something important about unary encoding. But I want to put that property into formal terms. It probably is identical to the property that all unary numbers contain all previous unary numbers as a prefix, and so it may not be very interesting in the end, but I just want that property stated in terms of the work a unary number can do in terms of encoding a program. So I will formalize the model a bit and see what the statement of the theorem should be:

Standard RAM can be abstracted as an oracle that can answer the question "Is bit X a 1?" truthfully every time. (Never mind that most modern RAM requires this question to be asked of 32-64 contiguous bits at a time; the abstraction is sound.) So, let's create a unary RAM oracle. One that would have to answer "yes" or "no" to every such question because they are not the class of questions it was designed to decide. Instead, we'll use an oracle that can answer the questions "Does file X start at this unit?" and "Does file X end at this unit?" By not giving it enough information to answer the question "Does file X contain this unit?" we make it weaker than even a membership oracle. All it can do is tell you whether you've guessed where the boundaries are. This assumption rules out my solution above that runs in time logarithmic in the length of the program.

Now, for simplicity, we'll assume there's a table somewhere that tells us where all the files (programs) start: Someone else has already done the work of locating them for us. In particular, we already know that unit Y is the beginning of program X.

So, the question is this: If program X has length n (n unknown for now), how much of program X can be run before n is determined? Yakk says we could execute as much of it we wanted by the time we know that the program is at least n-1 long, but this is unsatisfying, since we've basically read the whole thing anyway before we've even started running the program. So, let's ask this question instead: Assuming that we can only execute c instructions every time we query the RAM oracle, what's the maximum amount of program X we could have executed by the time we have definitively determined what n is (and therefore, what X does)?

We will assume, of course, that we do not do any more oracle queries than necessary to determine n. In particular, we will take no more than n-1 queries, since a sequential search will achieve this. I am pretty sure that a sequential search is the best we can do, but I'd like to see that formalized.

There is a missing assumption here that would make it easier to answer the main question: how does the number n encode its instructions? I think a reasonable assumption is that each instruction requires knowing a constant number of the bits of n's binary representation to execute, and as such, n encodes a program with O(log(n)/k) instructions.

Yakk, could you please repeat your analysis in this model?

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Unary Processor

Postby Yakk » Sun Sep 05, 2010 2:36 am UTC

The abstraction you are using remains pretty sloppy.

What I did was I used a pretty standard trick that works on pretty much any Turing Machine. It is, however, ridiculously inefficient -- but when you talk about "can X happen" you usually are not concerned with cost. :)

A unary turing machine with a single tape is, I suspect, about as powerful as a push-down automata -- ie, it is no longer Turing Complete. However, if you had an arbitrary Turing Machine with an additional instruction tape, it would behave much more similarly to a standard computer with a really crappy input method.

In short, I am not very clear what your proposed machine is, or what it can do.

And having a solid abstraction of what the machine is, and what it can do, is sort of required to reason about it.

With a standard TM, the difference between one set of instructions and operations and memory access features and another is just a matter of speed. With a hypothetical unary machine, the difference could be much, much, much more.

With a standard TM, you can encode N tapes in one tape by a number of methods -- with a some models of unary TM, this does not seem possible.

So, have you seen the set theoretic definition of Turing Machine?
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

squareroot
Posts: 548
Joined: Tue Jan 12, 2010 1:04 am UTC
Contact:

Re: Unary Processor

Postby squareroot » Sun Sep 05, 2010 4:14 am UTC

I've been trying to work out some very basic problems in a unary turing machine... in other words, 1 and EMPTY are the only two. Addition is simpler:
>111E11
Propagate rightwards and write "one", unless it's a second E, then go one left and erase.

Multiplication could probably done something like this:
>....EEEE111E1111EEEE... -> ....EEEE11E1111EE1111EEEE.... -> ....EEEE1E1111EE11111111EEEEE... -> ...EEE1111EE111111111111EEE... -> ...EEEE1111E111111111111EEEE...
That's, of course, already skipping many steps.

I think that at some point it was proved that if a system go do all of a certain list of actions, then it was turing complete... :?:
<signature content="" style="tag:html;" overused meta />
Good fucking job Will Yu, you found me - __ -

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Unary Processor

Postby Yakk » Sun Sep 05, 2010 5:03 pm UTC

See, 1 and E, if you can write E and have symbols to the 'right' of it, is a binary system.

You encode end of tape as EE. You encode 1 as 11 and 0 as 1E. E1 isn't used.

Turing machine computation is highly fragile -- it is really hard to avoid becoming a full power, pretty much equivalent to every other, Turing machine.

Which is why what I'm wondering what exactly is meant by a unary processor. :) You have to be very careful, or the answer is "it is just like any other processor".
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

squareroot
Posts: 548
Joined: Tue Jan 12, 2010 1:04 am UTC
Contact:

Re: Unary Processor

Postby squareroot » Sun Sep 05, 2010 6:41 pm UTC

Ah, okay that helps me understand!
So, how would a unary processor work? It's given a string of only 0's as input (the program to run), and it can do computation then on a binary tape... and returns the output in unary again? Or would it need to do all of it's computation using a unary, variable length register?
<signature content="" style="tag:html;" overused meta />
Good fucking job Will Yu, you found me - __ -

User avatar
Sizik
Posts: 1251
Joined: Wed Aug 27, 2008 3:48 am UTC

Re: Unary Processor

Postby Sizik » Sun Sep 05, 2010 6:57 pm UTC

I think the simplest way to have a strictly unary processor would be to have a lookup table with an entry for each possible input.
she/they
gmalivuk wrote:
King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Unary Processor

Postby quintopia » Sun Sep 05, 2010 8:59 pm UTC

Yakk: I was purposefully trying to avoid the nature of the machine doing the computation, limiting myself only to specifying how programs are stored, but yes, I am quite familiar with Turing Machines and pretty much every theorem concerning them. You may assume whatever sort of machine you want that does computation using any sort of number system you like, as long as you know it can only perform c instructions (or state transitions if you like) for every unit of program fetched from memory (or the instruction tape if you like). Any looseness of this model that concerns you, feel free to tighten it up with your own assumptions, with one (not-hard-to-achieve) caveat: the machine should be universal.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Unary Processor

Postby Yakk » Mon Sep 06, 2010 3:38 pm UTC

Well then, yes, you can still do useful work.

It ends up being not that useful, but ...

So we have a unary storage mechanism. The easy way to think of this is that we enumerate all of the programs in some way, and it stores the "program number" that we are going to run.[2]

Then it takes us K*program number time to determine which program we are running.

I think it is pretty easy to show using information theory that we cannot determine what even the first instructions are before we are finished. Basically, there are too many pigeons with a given starting sequence of instructions to fit them all in the start of the enumeration, if that really hand-wavey proof does anything for you.[3]

This also basically means we are deep in the Turing tar pit -- and how we encode the programs only matters up to a constant factor (we could, after all, choose a program that starts with a UTM[1] that then uses the rest of the data to encode a different program).

Despite this, we can do useful work. We only have a finite number of instructions per program number we rule out, but we could have a large amount of storage[4].

So what we do is we start simulating the prefix instructions of every program, and store the resulting state.

As the number of program prefixes grows exponentially, while the time we have to do this grows linearly, this means by the time we reach program K we will have simulated, on the hand-wavey order, of the first lg(K) steps of the program prefixes of length lg(K) (with maybe a square root thrown in there).

[1] Universal Turing Machine
[2] This is a pretty standard trick -- in this case, it is a bit awkward due to the unary storage method, but it probably remains the best choice.
[3] Imagine if we could rule out some sequence of prefix options after a fixed amount of nibbles n. But that prefix has tails that are arbitrary in length -- take that prefix, and append onto it n different suffixes. Not all of them could have been in the nibbles we read over -- there isn't enough information to rule each of them out -- so we clearly didn't rule all of them out.
[4] This could take ridiculous amounts of storage. It might be amusing to calculate how much!
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
Sizik
Posts: 1251
Joined: Wed Aug 27, 2008 3:48 am UTC

Re: Unary Processor

Postby Sizik » Tue Sep 07, 2010 9:52 pm UTC

cogman wrote:and how do you differentiate between III + IIII and IIIIII + III. How do you let the system know "Hey, we are doing this." Even just counting implies that there is some sort of identifier that signals that no more things exists (the non presence of something is datam).


How do you differentiate between 111 + 1000 and 1010 + 111?

cogman wrote:I'm sorry, but WHAT? You CAN'T have a unary computer that does anything. Ever every single symbol is the same, you end up with a system that has no way of telling what is going on. The moment you introduce any sort of method to distinguish one instruction from another, you have created a binary system (with distinguisher and the other symbols being 1s and 0s). A unary system that does any computation just can not exist as it will only have one state (on).


I'm sorry, but WHAT? You CAN'T have a binary computer that does anything. Every single symbol is either 1 or 0, you end up with a system that has no way of telling what is going on. The moment you introduce any sort of method to distinguish one instruction from another, you have created a ternary system (with distinguisher and the other symbols being 2s, 1s, and 0s). A binary system that does any computation just can not exist as it will only have two states (on or off).
she/they
gmalivuk wrote:
King Author wrote:If space (rather, distance) is an illusion, it'd be possible for one meta-me to experience both body's sensory inputs.
Yes. And if wishes were horses, wishing wells would fill up very quickly with drowned horses.

squareroot
Posts: 548
Joined: Tue Jan 12, 2010 1:04 am UTC
Contact:

Re: Unary Processor

Postby squareroot » Tue Sep 07, 2010 10:51 pm UTC

Sizik wrote:
cogman wrote:I'm sorry, but WHAT? You CAN'T have a unary computer that does anything. Ever every single symbol is the same, you end up with a system that has no way of telling what is going on. The moment you introduce any sort of method to distinguish one instruction from another, you have created a binary system (with distinguisher and the other symbols being 1s and 0s). A unary system that does any computation just can not exist as it will only have one state (on).


I'm sorry, but WHAT? You CAN'T have a binary computer that does anything. Every single symbol is either 1 or 0, you end up with a system that has no way of telling what is going on. The moment you introduce any sort of method to distinguish one instruction from another, you have created a ternary system (with distinguisher and the other symbols being 2s, 1s, and 0s). A binary system that does any computation just can not exist as it will only have two states (on or off).

I'm sorry, but WHAT? You CAN'T just requote someone with small differences in an attempt to display why their reasoning is false. Here, the key change is between "is the same" and "is either a 1 or a 0". That's a BIG difference.
<signature content="" style="tag:html;" overused meta />
Good fucking job Will Yu, you found me - __ -

Notch
Posts: 318
Joined: Tue Dec 12, 2006 5:52 pm UTC
Location: Stockholm, Sweden
Contact:

Re: Unary Processor

Postby Notch » Wed Sep 08, 2010 1:18 pm UTC

It's possible to store arbitrary data in an integer without knowing the value of the integer.

The simplest example would be to treat the integer as a queue of 1 bit values:

Code: Select all

// Returns input%2 and sets input to input/2
public Pile nextBit(Pile input) {
   Pile output;
   Pile copy;
   // Put every other bit into copy, and toggle output between 0 and 1
   while (!input.empty) {
      input--;
      if (output.empty) {
         output++;
      } else {
         output--;
         copy++;
      }
   }
   // Copy the result back into input (which was modified)
   while (!copy.empty) {
      copy--;
      input++;
   }
}


If you had some way of magically generating and discarding of eggs from piles, this could easily be implemented in hardware. Reading the lowest 8 bits is also possible, but takes up more space.
If you bitshift (trivial) the result of this method call by a large number then add it to input, you've got a cyclic tape.

userxp
Posts: 436
Joined: Thu Jul 09, 2009 12:40 pm UTC

Re: Unary Processor

Postby userxp » Wed Sep 08, 2010 2:54 pm UTC

squareroot wrote:
Sizik wrote:
cogman wrote:I'm sorry, but WHAT? You CAN'T have a unary computer that does anything. Ever every single symbol is the same, you end up with a system that has no way of telling what is going on. The moment you introduce any sort of method to distinguish one instruction from another, you have created a binary system (with distinguisher and the other symbols being 1s and 0s). A unary system that does any computation just can not exist as it will only have one state (on).


I'm sorry, but WHAT? You CAN'T have a binary computer that does anything. Every single symbol is either 1 or 0, you end up with a system that has no way of telling what is going on. The moment you introduce any sort of method to distinguish one instruction from another, you have created a ternary system (with distinguisher and the other symbols being 2s, 1s, and 0s). A binary system that does any computation just can not exist as it will only have two states (on or off).

I'm sorry, but WHAT? You CAN'T just requote someone with small differences in an attempt to display why their reasoning is false. Here, the key change is between "is the same" and "is either a 1 or a 0". That's a BIG difference.

I'm sorry, but WHAT? You CAN'T quote a quoted quotation like this in an attempt to display why someone's reasoning is false. People will pay more attention to the quoting of the quoted quotation than to your reasoning.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Unary Processor

Postby quintopia » Wed Sep 08, 2010 5:08 pm UTC

Notch wrote:It's possible to store arbitrary data in an integer without knowing the value of the integer.


The question wasn't whether we need to know the value of the integer to extract its data, but rather, whether we needed to load the whole thing from memory. In fact, the code you posted "implicitly" knows the value of the integer, since another function could extract that value from the program without changing it at all. (For instance, if I knew how long queue and arithmetic operations took, I could write a constant time program "getValue" that converts a length of time into the number of units read from the queue and just run "time ./nextBit inputFile | ./getValue" to recover the number your program supposedly didn't know.)

Yakk: Is the simulation you are suggesting as such:

Code: Select all

i=0;
while (file.hasMoreUnits()) {
  file.readOneUnit();
  remainingTime=c;
  finished=false;
  foreach (program p: p.length()<=i) {
     p.step(min(remainingTime,i));
     remainingTime-=i;
     if (remainingTime<0) break;
     finished=true;
   }
   if (finished) {
     i++;
     nullProgram.step(remainingTime);
   }
}


c is, as stated above, the number of simulated program instructions executable between reads of one unit from memory.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Unary Processor

Postby Yakk » Wed Sep 08, 2010 6:30 pm UTC

Programs in the above are encoded in binary.
The programs being run are Turing machine programs with a single tape, to keep the problem conceptually simple.

Code: Select all

void unary_runner( Future read_program )
{
  ProgramPrefixes prefixes;
  while( !read_program.done() )
    // advances the least-stepped program by 1 step.
    // If it reads from beyond the end of the tape, a pair of prefixes are spawned
    // and added to the ProgramPrefixes collection, and then one is advanced.
    prefixes.shortest().advance();
  }
  integer i = read_program.evaluate();
  Program p = Program::unpack(i); // find program number i
  ProgramPrefix pre = prefixes.match(p); // find the prefix that matches the head of program p
  p.advance_to( pre ); // advance the program based off of the already-executed part of prefix pre
  p.execute(); // run until finished
}

most of the pseudo-code should be self explanatory. I assumed a multithreading system for the environment, and used futures, because that makes the code easier to write. :)

If you really cared about keeping it O(1) per loop, you'd have to make sure that the prefixes.shortest().advance() didn't contain any ln-time or worse code.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Unary Processor

Postby quintopia » Wed Sep 08, 2010 8:36 pm UTC

Yeah, I realized just now that my code above was not what I meant. I meant something more like this:

Code: Select all

count=0;
l=0;
for (int i=0; true; i++) {
  for (int j=i; j>l; j--) {
    for  (int k=0;k<i;k++) {
      if (count%c==0) {
        if (progFile.currentUnit()==EOF) break;
        progFile.advance();
        count=0;
        l++;
      }
      Programs.get(j).step();
      count++;
    }
  }
}


In other words, it does 1 step on program 1, 2 steps on program 2, 2 steps on program 1, 3 steps on program 3, 3 steps on program 2, 3 steps on program 1, etc. etc. etc. and every c steps, it reads a unit and increases the lower bound on the programs it bothers to step. I'm guessing it's asymptotically equivalent to yours.

User avatar
Yakk
Poster with most posts but no title.
Posts: 11128
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Unary Processor

Postby Yakk » Wed Sep 08, 2010 8:41 pm UTC

*nod* -- and your multi-nested looped code is why I like abstracting away state. :) All I need to know is that implementing the abstraction efficiently is possible, and then the main path of code is clean and uncluttered.

In a more realistic unary model (realistic unary heh), I/O is going to be asynchronous with processing. Procedural code like yours has to be a lie in order to deal with asynchronous I/O (it has to predict what you want in the future, buffer up future reads, and then you only actually read from that buffer -- resulting in the first call being blocked until the buffer is filled. Then it has to predict that you'll want further data, and start loading that... otherwise, your code ends up blocked on I/O).

But that is just me over-engineering psuedo-code. ;)
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Unary Processor

Postby quintopia » Wed Sep 08, 2010 9:16 pm UTC

this is why i chose the model i did, where there is guaranteed to be a unit readable every c simulated steps.


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 5 guests