@Cowsquack it doesn't have I/O, but it's fairly easy to define a halt state via simple objective means; my original proof divides the tape into sections and only halting programs will cross from a section into the section before; I think it's possible to improve the proof so that halting is defined as falling off the leftmost end of the tape (as it happens, you only need a semi-infinite tape for TCness)
@ais523 perhaps I don't understand what a universal tm really is, but in what sense does it model the input taking part? is the "input" baked into the program or does it not need input for universal tc-ness?
it doesn't model the input taking part, that isn't a requirement for TCness
instead, you compile your program from some other language (e.g. cyclic tag) into an initial state for the 2,3 machine, then run it to see if it halts
it's a pretty complex compilation, the initial state is infinitely long and has a complicated nested pattern
meaning that the 2,3 machine tends to be useless for proving things TC because generating the pattern is nearly always going to be more complex than just using a more complex Turing machine
@ais523 ah so that halting condition is what wikipedia means by "and the claim is open to debate when taking into consideration traditional definitions of universality and whether the relaxing of the Turing machine properties used for the proof can be allowed in general and may even suggest novel ways to define computational universality more independent of arbitrary choices"
it's more the initial state than the halt test that needs relaxing in this case, but yes, the big debate is about how much relaxation you're allowed before you're no longer proving TCness
this isn't objectively defined and it's hard to define objectively
(at)Veskah Good for you. I hope you won't become tired like that day.
The sequence 1, 2, 3, ..., n gets pushed to a stack. The stack will be outputted via an iteration of outputting the top of the stack and popping the stack. Write a formula predicting what will the ith number be in the output.
911 is operated by what is essentially a specialized call center. The employees who take the calls are called operators, and they pass the calls on, or dispatch them, to the relevant emergency services
CMC: Microwave time code-golf. Given an input number of seconds, output the time that would show on a microwave, using the convention that 1:00 means 60 seconds. Examples: 60 -> 1:00 ... 65 -> 1:05 ... 200 -> 3:20
@cairdcoinheringaahing I just noticed that - curiously - Doppelgänger is not the opposite of Einzelgänger, those two actually have quite unrelated meanings.
Effective today, all Subscriber Content on Stack Overflow and the Stack Exchange network will be available under the terms of version 4.0 of the Creative Commons Attribution-ShareAlike (CC BY-SA) license.
This change follows our last Terms Of Service (ToS) update where we inadvertently introduce...