6 ms·
> The task is not that; instead we assume that we already have a table that correctly describes the TM's maps from bounded input to output when they terminate.
by giomasce 6y ago
> The task is not that; instead we assume that we already have a table that correctly describes the TM's maps from bounded input to output when they terminate. His claim is that this table can be expressed as a function in addition and multiplication with the input as operands.
Ok, if the task is this then everything is very easy, I agree. I was commenting on a much harder task, i.e., converting a generic TM to a function adding and multiplying the inputs. That is something you can't do.
> is false, we can simply encode it as the encoded tuple of the TM and the input; this is a standard construct when we talk about simulating TMs with a UTM.
I don't see how that disproves my assertion. I was saying something different, which has to do with your (correct) first assertion: a TM cannot establish if another TM is going to terminate on a certain input.
- jhanschoo 6y ago> I was saying something different It's important to be precise with language; said encoding is a description of a given TM on a particular input, since a map exists from it to the space of outputs union DOESNOTTERMINATE. Now, whether or not this map is a computable function is a different question.