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

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