News for hackers. Stuff that matters.
Re:Emit-C: A time travelling programming language by openasocket on Friday November 15, 2024 @05:49PM (#42152173)
Surprisingly there is prior work on this! https://www.scottaaronson.com/papers/ctchalt.pdf . Apparently a Turing Machine with time travel can solve the halting problem
Re:Emit-C: A time travelling programming language by fragmede on Friday November 15, 2024 @06:30PM (#42152506)
With time travel, isn't the halting problem trivially solvable? You start the program, and then just jump to after the end of forever and see if the program terminated.
Re:Emit-C: A time travelling programming language by JadeNB on Friday November 15, 2024 @07:10PM (#42152855)
> With time travel, isn't the halting problem trivially solvable? You start the program, and then just jump to after the end of forever and see if the program terminated.

Some programs won't halt even after forever, in the sense of an infinite number of time stops. For example, if you want to test properties of (possibly infinite) sets of natural numbers, there's no search strategy that will go through them even in infinite time.

(Footnote that I'm assuming, I think reasonably but who knows what CSists have been up to?, a model of computation that allows the performance of countably, but not uncountably, many steps.)

Re:Emit-C: A time travelling programming language by eddd-ddde on Friday November 15, 2024 @07:41PM (#42153042)
But if you are at the present, and dont receive a future result immediately, can't you assume it never halts? Otherwise you would have received a result.
Re:Emit-C: A time travelling programming language by mgsouth on Friday November 15, 2024 @08:17PM (#42153303)
I don't think so. That's assuming the program will always be in a frame of reference which is temporally unbounded. If, for example, it fell into a black hole it would, IIUC, never progress (even locally) beyond the moment of intercepting the event horizon.
Re:Emit-C: A time travelling programming language by eddd-ddde on Saturday November 16, 2024 @08:44PM (#42161287)
Hmmm, couldn't you, as long as there's a fixed period of time that supports time travel, keep execution working by travelling to the start of the period again and again (/with/ the current program state) to avoid the program from going beyond the working time period?
Re:Emit-C: A time travelling programming language by mgsouth on Wednesday November 20, 2024 @12:52AM (#42191141)
Ooh, clever. Vaguely envision entropy problems, that some mash-up of Godel's Incompleteness theorem, Maxwell's Demon, and Bell's Inequality, and Newton's laws conspires against it. Maybe sending changes back add entropy, or moves it around? Would make a good old-school SF story, with backwater multi-verse dumps for waste entropy, a free-lance troubleshooter uncovering a secret corporate scandal regarding deleterious effects, etc.
Re:Emit-C: A time travelling programming language by pino999 on Saturday November 16, 2024 @06:11AM (#42155828)
It goes like this: We have two observers with a computer. A is outside a black hole. B goes over the event horizon. B is infinitely time dilated seen from A. It takes forever for B to reach the singularity from A standpoint. B reaches the middle in a finite time.

A starts computation. If it halts A sends a result, otherwise it won't.

B sees the result in a finite time. If it doesn't, the program didn't halt.

If time is discrete, it won't fly I think. This works because there is no smallest time unit in gr.

We are working with different types of infinities. A's computational steps take, the further B goes in, less time. Sort of Zeno's paradox. It is easy to map all natural numbers between 0 and 1 on the real line. Just not 1 to 1.

There are more problems.

How to get the information out and how to survive the divergent blue shift, it is somewhat unclear. B cannot talk back. But still a cool find.

Re:Emit-C: A time travelling programming language by JadeNB on Saturday November 16, 2024 @01:12PM (#42157923)
> It is easy to map all natural numbers between 0 and 1 on the real line. Just not 1 to 1.

For the usual meaning of the term, you certainly can construct a 1-to-1 (that is, injective) map N \to [0, 1] (for example, n \mapsto 10^(-n)); the natural numbers just can't be mapped onto [0, 1] (that is, the map can't be surjective). That's the opposite of the problem we have: it's saying you can losslessly encode a countable amount of information in an uncountable amount of space; but I'm saying conversely that you can't perform an uncountable number of steps in a countably infinite amount of time.

Re:Emit-C: A time travelling programming language by pino999 on Monday November 18, 2024 @11:13AM (#42173782)
But the computation steps are certainly countable, even if there are infinite. The amount of steps in time we can take is uncountable. We can always find a point between two other times.Time dilation does exactly this, making the time a computational step take smaller and smaller.
Re:Emit-C: A time travelling programming language by HeliumHydride on Friday November 15, 2024 @06:48PM (#42152664)
I think you can only time travel a finite time.
Re:Emit-C: A time travelling programming language by MadnessASAP on Friday November 15, 2024 @08:49PM (#42153437)
That's why you instead specify that if & when the program halts it travels back in time to let you know it has. Thus you would know immediately after starting the computation if it's going to halt, how long it'll take, and what the result is.

Of course you should still carry out the computation to prevent a paradox.

Re:Emit-C: A time travelling programming language by PittleyDunkin on Saturday November 16, 2024 @12:59AM (#42154682)
Surely we already have this: the jump just takes forever.