AlephNeil comments on A simple counterexample to deBlanc 2007? - Less Wrong

3 Post author: PhilGoetz 30 May 2011 05:09AM

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

Article Navigation

Comments (40)
Tags: fai math utility

Comments (40)

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

Comment author: AlephNeil 30 May 2011 03:28:09PM 4 points [-]

Goedel numbers are integers; how could anything that is enumerated by Goedel numbers not be enumerable? S_I, S, and R are all enumerable. The original paper says that R is the set of partial mu-recursive functions, which means computable functions; and the number of computable functions is enumerable.

You seem to be using 'enumerable' to mean 'countable'. (Perhaps you're confusing it with 'denumerable' which does mean countable.)

RichardKenneway means "recursively enumerable".

Comment author: PhilGoetz 30 May 2011 04:40:32PM *  0 points [-]

You're right! But I may still be right that the set of functions in R is enumerable. (Not that it matters to my post.)

There is a Turing function that can take a Goedel number, and produce the corresponding Goedel function. If you can define a programming language that is Turing-complete, and for which all possible strings are valid programs, then you just turn this function loose on the integers, and it enumerates the set of all possible Turing functions. Can this be done?

Comment author: AlephNeil 31 May 2011 11:56:06AM 1 point [-]

Sure, R is recursively enumerable, but S and S_I are not.

Powered by Reddit Powered by Reddit