= 27d567bc2d48d9f40e9ccc20ea370b15)
Pfft comments on Open thread, Sep. 26 - Oct. 02, 2016 - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (90)
The claim as stated is false. The standard notion of a UTM takes a representation of a program, and interprets it. That's not primitive recursive, because the interpreter has an unbounded loop in it. The thing that is is primitive recursive is a function that takes a program and a number of steps to run it for (this corresponds to the U and T in the normal form theorem), but that's not quite the thing that's usually meant by a universal machine.
I think the fact that you just need one loop is interesting, but it doesn't go as far as you claim; if an angel gives you a program, you still don't know how many steps to run it for, so you still need that one unbounded loop.
Nope. The standard notion of a UTM take the representation of a program and an input, and interprets it. With the caveat that those representations terminate!
What you say, that the number given to the UTM is the number of steps for which the machine must run, is not what is asserted by Kleene's theorem, which is about functions of natural numbers: the T relation checks, primitive recursively, the encoding of a program and of an input, which is then fed to the universal interpreter.
You do not say to a Turing machine for how much steps you need to run, because once a function is defined on an input, it will run and then stop. The fact that some partial recursive function is undefined for some input is accounted by the unbounded search, but this term is not part of the U or the T function.
The Kleene equivalence needs, as you say, unbounded search, but if the T checks, it means that x is the encoding of e and n (a program and its input), and that the function will terminate on that input. No need to say for how much steps to run the function.
Indeed, this is true of and evident in any programming language: you give to the interpreter the program and the input, not the number of steps.
See wikipedia. The point is that T does not just take the input n to the program to be run, it takes an argument x which encodes the entire list of steps the program e would execute on that input. In particular, the length of the list x is the number of steps. That's why T can be primitive recursive.
From the page you link:
Also from the same page: