{
localUrl: '../page/rice_and_halt.html',
arbitalUrl: 'https://arbital.com/p/rice_and_halt',
rawJsonUrl: '../raw/5n6.json',
likeableId: '3305',
likeableType: 'page',
myLikeValue: '0',
likeCount: '2',
dislikeCount: '0',
likeScore: '2',
individualLikes: [
'EricBruylant',
'VladArber'
],
pageId: 'rice_and_halt',
edit: '4',
editSummary: '',
prevEdit: '3',
currentEdit: '4',
wasPublished: 'true',
type: 'wiki',
title: 'Rice's theorem and the Halting problem',
clickbait: '',
textLength: '2460',
alias: 'rice_and_halt',
externalUrl: '',
sortChildrenBy: 'likes',
hasVote: 'false',
voteType: '',
votesAnonymous: 'false',
editCreatorId: 'JaimeSevillaMolina',
editCreatedAt: '2016-08-14 19:22:24',
pageCreatorId: 'JaimeSevillaMolina',
pageCreatedAt: '2016-07-29 13:53:51',
seeDomainId: '0',
editDomainId: 'AlexeiAndreev',
submitToDomainId: '0',
isAutosave: 'false',
isSnapshot: 'false',
isLiveEdit: 'true',
isMinorEdit: 'false',
indirectTeacher: 'false',
todoCount: '0',
isEditorComment: 'false',
isApprovedComment: 'true',
isResolved: 'false',
snapshotText: '',
anchorContext: '',
anchorText: '',
anchorOffset: '0',
mergedInto: '',
isDeleted: 'false',
viewCount: '159',
text: 'We will show that [5mv Rice's theorem] and the [46h the halting problem] are equivalent.\n\n#The Halting theorem implies Rice's theorem\nLet $S$ be a non trivial set of computable partial functions, and suppose that there exists a Turing machine encoded by $[n]$ such that:\n$$\n[n](m) = \n\\left\\{\n \\begin{array}{ll}\n 1 & [m] \\text{ computes a function in $S$} \\\\\n 0 & \\text{otherwise} \\\\\n \\end{array}\n \\right.\n$$\n\nWe can assume [without_loss_of_generality w.l.o.g.] that the empty function undefined on every input is not in $S$ \n%%note:Suppose that the empty function is in $S$. Then it is satisfied that the empty function is **not** in $S^c$, and if $S$ is decidable then it follows immediately that [the_complement_of_a_decidable_set_is_decidable $S^c$ is decidable as well]. So we can use $S^c$ as our $S$ and the argument follows exactly the same.%%. \nThus there exists a computable function in $S$ computed by some machine $[s]$ such that $[s](x)$ is defined for some input $x$.\n\nSuppose we want to decide whether the machine $[m]$ halts on input $[x]$.\n\nFor that purpose we can build a machine $Proxy_s$ which does the following:\n\n Proxy_s(z):\n call [m](x)\n return s[z]\n\nClearly, if $[m](x)$ halts then Proxy_z computes the same function as $[s]$, and thus $[n](Proxy_s)=1$.\n\nIf on the other hand $[m](x)$ does not halt, then Proxy_s(z) computes the empty function, which we assumed to not be in $S$, and therefore $[n](Proxy_s)=0$.\n\nThus we can use a Turing machine computing pertinence to $S$ to decide the halting problem, which we know is undecidable. We conclude that such a machine cannot possibly exists, and thus Rice's theorem holds.\n\n\n#Rice's Theorem implies the Halting theorem\nSuppose that there was a Turing machine $HALT$ deciding the Halting Problem.\n\nLet $S$ be the set of computable functions defined on a fixed input $x$, which is clearly non-trivial, as it does not contain the empty function but is not empty either. Let $[n]$ be a Turing machine, and we want to decide whether $[n]\\in S$ or not. If this was possible for an arbitrary $[n]$, then we would have reached a contradiction, as Rice's theorem forbids this outcome.\n\nBut $[n]$ belongs to $S$ iff $[n]$ halts on input $x$, so we can use $HALT$ to decide whether $[n]$ belongs to $S$, in contradiction with Rice's theorem. So our supposition of the existence of $HALT$ was erroneous, and thus the Halting theorem is true.',
metaText: '',
isTextLoaded: 'true',
isSubscribedToDiscussion: 'false',
isSubscribedToUser: 'false',
isSubscribedAsMaintainer: 'false',
discussionSubscriberCount: '1',
maintainerCount: '1',
userSubscriberCount: '0',
lastVisit: '',
hasDraft: 'false',
votes: [],
voteSummary: [
'0',
'0',
'0',
'0',
'0',
'0',
'0',
'0',
'0',
'0'
],
muVoteSummary: '0',
voteScaling: '0',
currentUserVote: '-2',
voteCount: '0',
lockedVoteType: '',
maxEditEver: '0',
redLinkCount: '0',
lockedBy: '',
lockedUntil: '',
nextPageId: '',
prevPageId: '',
usedAsMastery: 'false',
proposalEditNum: '0',
permissions: {
edit: {
has: 'false',
reason: 'You don't have domain permission to edit this page'
},
proposeEdit: {
has: 'true',
reason: ''
},
delete: {
has: 'false',
reason: 'You don't have domain permission to delete this page'
},
comment: {
has: 'false',
reason: 'You can't comment in this domain because you are not a member'
},
proposeComment: {
has: 'true',
reason: ''
}
},
summaries: {},
creatorIds: [
'JaimeSevillaMolina'
],
childIds: [],
parentIds: [
'rice_theorem'
],
commentIds: [
'5p3',
'5vp'
],
questionIds: [],
tagIds: [
'work_in_progress_meta_tag'
],
relatedIds: [],
markIds: [],
explanations: [],
learnMore: [],
requirements: [],
subjects: [],
lenses: [],
lensParentId: 'rice_theorem',
pathPages: [],
learnMoreTaughtMap: {},
learnMoreCoveredMap: {},
learnMoreRequiredMap: {},
editHistory: {},
domainSubmissions: {},
answers: [],
answerCount: '0',
commentCount: '0',
newCommentCount: '0',
linkedMarkCount: '0',
changeLogs: [
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '18735',
pageId: 'rice_and_halt',
userId: 'JaimeSevillaMolina',
edit: '4',
type: 'newEdit',
createdAt: '2016-08-14 19:22:24',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '18731',
pageId: 'rice_and_halt',
userId: 'JaimeSevillaMolina',
edit: '3',
type: 'newEdit',
createdAt: '2016-08-14 15:27:40',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '3261',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '1',
dislikeCount: '0',
likeScore: '1',
individualLikes: [],
id: '17769',
pageId: 'rice_and_halt',
userId: 'JaimeSevillaMolina',
edit: '2',
type: 'newEdit',
createdAt: '2016-07-30 00:21:02',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '17722',
pageId: 'rice_and_halt',
userId: 'JaimeSevillaMolina',
edit: '0',
type: 'newParent',
createdAt: '2016-07-29 13:53:53',
auxPageId: 'rice_theorem',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '17723',
pageId: 'rice_and_halt',
userId: 'JaimeSevillaMolina',
edit: '0',
type: 'newTag',
createdAt: '2016-07-29 13:53:53',
auxPageId: 'work_in_progress_meta_tag',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '17720',
pageId: 'rice_and_halt',
userId: 'JaimeSevillaMolina',
edit: '1',
type: 'newEdit',
createdAt: '2016-07-29 13:53:51',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
}
],
feedSubmissions: [],
searchStrings: {},
hasChildren: 'false',
hasParents: 'true',
redAliases: {},
improvementTagIds: [],
nonMetaTagIds: [],
todos: [],
slowDownMap: 'null',
speedUpMap: 'null',
arcPageIds: 'null',
contentRequests: {}
}