Talk:TwoDucks

TwoDucks isn't necessarily uncomputable (I think)

If a time expression is encountered which alters something in an earlier time, then the interpreter could then rewind the program back to that time, change whatever is being altered, then fast-forward to where it was.

If this were to cause a paradox (i.e. stop the alteration of the past, or to change it), this could (although it probably won't be easy) be detected, and an error message displayed. "Paradox!" or something like that.

The main problem is I/O:

• Input could just be saved and re-entered when fast-forwarding. Or a new input prompt could be created.
• Output could be removed from the display when rewinding, and reprinted (with whatever changes) on fast-forward. Or the new output could just be displayed after the old.

Modifying stuff in the future is also possible - just save the potential alteration, and when the interpreter gets to the correct time, silently replace the value.

If, as suggested, the user stops the program if told that it does not halt, that could lead to the program saying that it doesn't halt because it was stopped, even if it would halt after a while. --(this comment by 109.148.239.1 at 14:18, 9 October 2011 UTC; please sign your comments with ~~~~)

This way of doing things does NOT allow you to solve the halting problem -- the test program will have to be run to completion before the assignment occurs -- there is no way to always tell if will terminate, until it does.

Alksentrs 21:53, 24 December 2007 (UTC)

• Actually, it does solve the halting problem, because it actually travels back in time. the problem is, it's impossible to implement (at least not on a turing machine, and maybe even physically impossible). if you tried implementing it, you're right that the program would have to run to completion first. anyway, awesome idea for a language.Afarnen 23:49, 27 February 2008 (UTC)

Couldn't the program be rewritten so that it works without time travel? When someone writes the actual code in the first place, he knows what should ultimately happen. We can tell that the second example should input then output, so why give the interpreter that power? Paradoxes could be handled specially. --Loki 20:48, 28 September 2009 (UTC)

---

As has been pointed out, it's possible to simulate the time travel by just caching sends to the future and applying the change when the time is right, and dealing with sends to the past by keeping track of the program state at each prior time and starting again from the state at the time the variable was sent to.

Alternately, you could consider that at each point in the the program execution, it's possible that any variable will change its value due to a send executed some time in the future. Now suppose that that the program can correctly guess whether a send will modify a variable at the current time and what it will be modified to, and then continue to execute as though that change had happened already. Then when/if the send is actually reached, it's a no-op.

These two ways of looking at the execution are almost identical to the two most common ways of thinking about how a nondeterministic Turing Machine works. And it's been shown that a NDTM is in the same computational class as a DTM; only the complexity classes they define are different. The important thing is that the simulator arrives at the same result as the real time-travelling interpreter would, not how it does it.

Finally note that the halting oracle example is only guaranteed to work if the code being tested does not use a SEND. The oracle itself does use a send however, and so it's not possible to determine if the oracle itself halts by feeding it as input to itself, and that's the sort of situation that makes the halting problem impossible to solve in the general case. You can make halting oracles that work in most cases on a regular Turing Machine, too. TwoDucks is computable and Turing-equivalent.

130.108.16.157 02:08, 27 February 2012 (UTC)

TwoDucks less SEND is still Turing-complete; therefore, the halting oracle is capable of determining whether any Turing machine halts. Thus, TwoDucks is uncomputable. Phantom Hoover 17:20, 27 February 2012 (UTC)

For this proof, I'm assuming that the thread scheduler and threaded programs are implemented in such a way that an arbitrary TwoDucks program will return the same result each time (or fail to halt each time). If it doesn't, it's not even a function, much less a computable one and is thus not relevant here. (It's entirely possible to write inconsistent programs in many other Turing Complete languages once hardware is taken into account, so I'm asserting that this is not of interest to the computability of the language itself.)

Now take a threaded program. For every variable that is changed by a given thread, append "_[i]" to the end of the variable name, where i is the number of the thread. Now take all instructions from all threads and merge them into a single thread in the order in which they are run according to one of the consistent schedules. We now have a single threaded program that computes the same result as the multithreaded one. For the rest of the proof, I'm going to work with single threaded programs only; multithreaded programs can be transformed to such first as needed.

Let F be the set of all possible TwoDucks programs, and let f be an arbitrary member of this set. When I say SEND, I'm referring to SENDs to the past. I don't think anyone's arguing that SENDs to the future add anything to the computational model. I'll amend the proof to include those if asked, but I'd rather not take the time if I don't have to.

Let S(f, x, t, T) be the program state of f with starting input x, as it exists at time t after T SENDs to the past have already been executed. S(...) = ( pc, v0, v1, ..., vm ) where pc is the program counter and vi is the value of variable i under some enumeration of the variables existing at that point of the program. Iff pc is after the last instruction or is on an END instruction, the program is in a halting state. Let G:S->S be the state transition function.

The program begins at S(f, x, 0, 0). Either it eventually hits a SEND or it doesn't. If it does, it does so at some fixed time t=i, simply because if it takes an infinite time to get there than the program is equivalent to a nonhalting SENDless program. If pc isn't a SEND q to j, then G(S(f, x, t, T)) = S(f, x, t+1, T). If pc is a send to time j, then G(S(f, x, t, T)) = S(f, x, j, T+1) and is the same as setting pc and the v vector to the value at S(f, x, j, T), then executing a SET q to (the value of q at time t). Since the SEND was executed after a finite number of steps and there are a finite number of variables, all this happens in a finite amount of time. Because of this equivalence, we can take a TwoDucks program and replace each SEND with a sequence of SETs and a GOTO. We now have a sendless TwoDucks program that does the same thing as the original one. (plus or minus output, but that can be handled by erasing previous output and replacing it with new values.)

Here we have the transformed version of the halting oracle:

SET halts TO 0

SET mark TO 1

NOUT halts

// Program goes here

SET halts TO 1

(erase last printed character)

NOUT halts

// Program goes here

SET halts TO 1

If the program halts, it'll print 0, then eventually erase that and print 1. If the program doesn't halt, it'll print 0 and loop forever. So at any given point before it replaces the 0 with a 1, you can't tell whether it's going to halt or not, and since nonhalting programs never halt, you'll never be able to say for sure whether that 1 will eventually show up. So this doesn't solve the halting problem.

Now let's look at the original form:

SET halts TO 0

SET mark TO 1

NOUT halts

// Program goes here

SET halts TO 1

SEND halts TO 1~0~{mark}=1

If the program halts, it'll print 0, then eventually a SEND will be sent back in time and 1 will be printed instead. If it doesn't halt, it'll print 0 and loop forever. If you see a 0, you have no way of telling whether you're in the original history and at some time in the future someone will go back in time and change that value, or if you're seeing a 0 because the program will loop forever and it'll never change. If you see a 1, you know it halts (and that time-travel has happened.) You're in essentially the same situation you were in in the sendless version; if you see a 0, you don't know for sure that it'll *stay* 0. The only difference is that if it does become 1, you'll remember it having been 0 in the sendless version but in the time-travel version you'll have only seen the 1.

It does seem like the answer may be dependent on what model of time-travel you're assuming. For the second time dimension or multiverse/many-worlds models, this proof holds (with a few modifications in the second case), but you could potentially come up with other self-consistent models under which either a different proof is needed or the language is genuinely uncomputable. If you have such a model, please post it.

130.108.16.157 19:05, 27 February 2012 (UTC)

"If the program halts, it'll print 0, then eventually a SEND will be sent back in time and 1 will be printed instead."

No — if the program halts, then it'll have printed 1 all along. That's the point of time travel: it changes it as it happens, not later on. —ehird 19:45, 27 February 2012 (UTC)

Only if you assume a single invariant timeline. If you use a model of time travel with a changing timeline, then there exists an original history from which the time traveller originally came, so to speak. In that history, the value is 0, whether or not the program halts. The question then becomes one of whether you're in the original timeline or not. So whether the program solves the halting problem is dependent on the model of time travel you're using, as I stated above. 130.108.16.157 14:56, 2 March 2012 (UTC)

---

Quantum Superposition

It's a bit unsatisfying to say a program that creates a paradox (such as the first example given) "doesn't work." In fact, such a situation is equivalent to a quantum superposition of states of a variable. So, the output of the example program should be all(0,1). That is, a quantum superposition where the value of the variable is equal parts 0 and 1. See what Damian Conway has to say on the subject.

Do you have a transcript of the video, please? --Zzo38 03:36, 6 October 2008 (UTC)

No. The thing's an hour long. --Quintopia 05:15, 9 October 2008 (UTC)

I solved the paradoxes in my similar language timefuck by using the many-worlds hypothesis.--alternative678 01:39, 11 December 2009 (UTC)

Time Expressions Ambiguity

"a~b~c b'th time since a is true that expression c is true (b=0 is first (right after it happens), b=1 second time, etc.) This can either refer to a time in the past or a time in the future." This could be interpreted two ways. Either it's looking for the time at which c has been true for b ticks, or it's looking for the "b"th time that c has *become* true.

0. SET x TO 0
1. SET x TO 1
2. SET y TO 2
3. SET x TO 0
4. SET x TO 1
5. SET y TO 1
6. SET t TO 1~1~{x}=1

Is t equal to 2 or 4? -130.108.16.157 20:25, 21 February 2012 (UTC)