Unary Processor

[quintopia]

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]

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.

[Xanthir]

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.)

[++$_]

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

That would mean that if you get to n, you couldn't execute any particular set of instructions, because you could be reading the program N, 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.

[quintopia]

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]

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]

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.

[quintopia]

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]

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.

[Xanthir]

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.

[cogman]

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]

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]

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!
[/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();
    }
  }
}

[WarDaft]

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.

[Yakk]

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.

[userxp]

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 .

[Sizik]

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?

[Notch]

Yes. Or Game of Life, or Minesweeper.

[Axidos]

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.

[quintopia]

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.

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...

[Thesh]

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.

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.

[quintopia]

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?

[Yakk]

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?

[squareroot]

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...

[Yakk]

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".

[squareroot]

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?

[Sizik]

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.

[quintopia]

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.

[Yakk]

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!

[Sizik]

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?

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).

[squareroot]

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.

[Notch]

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]

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.

[quintopia]

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.

[Yakk]

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.

[quintopia]

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.

[Yakk]

*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.

[quintopia]

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