3 ms·

And that's precisely what I challenged. You can't even describe a Turing machine on one single input (using whatever operations you like) if you're not able to

And that's precisely what I challenged. You can't even describe a Turing machine on one single input (using whatever operations you like) if you're not able to determine if that machine is going to terminate. And in general you are not (at least, I am not; if you are, I happen to have a few Turing machines for which I'd be happy to pay to know if they're going to terminate or not; good money, I promise).

jhanschoo 6y ago
You hold a misconception. 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. To be more precise, with the input and constant numbers (arbitrarily choosable while designing the description of the function) as operands. Incidentally, > You can't even describe a Turing machine on one single input (using whatever operations you like) 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.
- 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.

jhanschoo 6y ago

You hold a misconception. 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. To be more precise, with the input and constant numbers (arbitrarily choosable while designing the description of the function) as operands. Incidentally, > You can't even describe a Turing machine on one single input (using whatever operations you like) 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.

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.