You're looking at Less Wrong's discussion board. This includes all posts, including those that haven't been promoted to the front page yet. For more information, see About Less Wrong.

Pfft comments on Open thread, Sep. 26 - Oct. 02, 2016 - Less Wrong Discussion

2 Post author: MrMind 26 September 2016 07:41AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Article Navigation

Comments (90)

Comments (90)

You are viewing a single comment's thread. Show more comments above.

Comment author: Pfft 29 September 2016 02:45:19PM *  0 points [-]

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.

Comment author: MrMind 30 September 2016 06:56:01AM 0 points [-]

From the page you link:

The T predicate is primitive recursive in the sense that there is a primitive recursive function that, given inputs for the predicate, correctly determine the truth value of the predicate on those inputs.

Also from the same page:

This states there exists a primitive recursive function U such that a function f of one integer

Powered by Reddit Powered by Reddit