You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.
Joshua Meyers (Jan 15 2022 at 01:43):Consider infinite state machines, like finite state machines except infinite. An example of an infinite state machine is a Turing machine, where you consider the entire configuration (what's written on the tape, where is the head, what state is the head in) as the state.
There exist infinite state machines that can compute more than Turing machines. For example, let f be any function inputting and outputting finite bit sequences. Now consider a machine with one state for each finite bit sequence. The machine starts at the null sequence (). If the machine is at state (b0,...,bn) and you input a bit b, it transitions to state (b0,...,bn,b). If the machine is at state (b0,...,bn) and you input "eof" indicating that you are done with the input, then it outputs f(b0,...,bn). This machine computes a function which may not be computable by a Turing machine.
So the question is, can this sort of thing be done by a machine with countably many states? Or are all countable state machines simulable by Turing machines?
Zhen Lin Low (Jan 15 2022 at 02:00):Surely not. First we must say what it means for a countable state machine to simulable by a Turing machine. I think it is reasonable to say that it means there is an injective map from the set of states to the set of natural numbers and an injective map from the input alphabet to the set of natural numbers, such that the respective images are computable set and the transition function is (under this mapping) computable. (For simplicity I consider only deterministic state machines.) If you fix the mappings – because, say, the states and the input are already coded as numbers – then it seems clear that the transition function could end up being uncomputable. What is not clear to me is whether you can always choose some other mapping that makes the transition function computable... but I'm pretty sure it's not possible.
Joshua Meyers (Jan 15 2022 at 02:10):Yeah I agree it's not easy to come up with a way of doing this. But that doesn't mean it's impossible.
Also, my vision of a simulation has a map from states of the CSM (countable state machine) to tuples where are the values written on the tape, is the location of the head, and is the state of the head.
Joshua Meyers (Jan 16 2022 at 11:32):The answer is no! The example I gave is actually countable.