{ localUrl: '../page/evidence_for_CT_thesis.html', arbitalUrl: 'https://arbital.com/p/evidence_for_CT_thesis', rawJsonUrl: '../raw/4j7.json', likeableId: '2751', likeableType: 'page', myLikeValue: '0', likeCount: '4', dislikeCount: '0', likeScore: '4', individualLikes: [ 'EricBruylant', 'PatrickStevens', 'NateSoares', 'ConnorFlexman2' ], pageId: 'evidence_for_CT_thesis', edit: '5', editSummary: 'tidied up links, slight rewording', prevEdit: '4', currentEdit: '5', wasPublished: 'true', type: 'wiki', title: 'Church-Turing thesis: Evidence for the Church-Turing thesis', clickbait: 'Why do we believe in CT thesis?', textLength: '2069', alias: 'evidence_for_CT_thesis', externalUrl: '', sortChildrenBy: 'likes', hasVote: 'false', voteType: '', votesAnonymous: 'false', editCreatorId: 'EricBruylant', editCreatedAt: '2016-06-20 19:59:25', pageCreatorId: 'JaimeSevillaMolina', pageCreatedAt: '2016-06-17 19:17:43', seeDomainId: '0', editDomainId: 'AlexeiAndreev', submitToDomainId: '0', isAutosave: 'false', isSnapshot: 'false', isLiveEdit: 'true', isMinorEdit: 'false', indirectTeacher: 'false', todoCount: '3', isEditorComment: 'false', isApprovedComment: 'true', isResolved: 'false', snapshotText: '', anchorContext: '', anchorText: '', anchorOffset: '0', mergedInto: '', isDeleted: 'false', viewCount: '159', text: 'As the Church-Turing thesis is not a [ proper mathematical sentence] we cannot prove it. However, we can collect [-3s] to increase our confidence in its correctness.\n\n#The inductive argument\nEvery computational model we have seen so far is [ reducible] to Turing's model.\n\nIndeed, the thesis was originally formulated independently by Church and Turing in reference to two different computational models ([Turing_machines] and [Lambda_Calculus] respectively). When they were shown to be [equivilance_relation equivalent] it was massive evidence in favor of both of them.\n\nA non-exhaustive list of models which can be shown to be reducible to Turing machines are:\n\n* [Lambda_calculus]\n* [Quantum_computation]\n* [Nondeterministic_Turing_machines Non-deterministic_Turing_machines]\n* [Register_machines]\n* The set of [-recursive_functions]\n\n#Lack of counterexamples\nPerhaps the strongest argument we have for the CT thesis is that there is not a widely accepted candidate to a counterexample of the thesis. This is unlike the [-4ct], where quantum computation stands as a likely counterexample.\n\nOne may wonder whether the computational models which use a source of [ randomness] (such as quantum computation or [-probabilistic_Turing_machines]) are a proper counterexample to the thesis: after all, Turing machines are fully [-deterministic], so they cannot simulate randomness.\n\nTo properly explain this issue we have to recall what it means for a quantum computer or a probabilistic Turing machine to compute something: we say that such a device computes a function $f$ if for every input $x$ the probability of the device outputting $f(x)$ is greater or equal to some arbitrary constant greater than $1/2$. Thus we can compute $f$ in a classical machine, for there exists always the possibility of simulating every possible outcome of the randomness to deterministically compute the probability distribution of the output, and output as a result the possible outcome with greater probability.\n\nThus, randomness is reducible to Turing machines, and the CT thesis holds.', metaText: '', isTextLoaded: 'true', isSubscribedToDiscussion: 'false', isSubscribedToUser: 'false', isSubscribedAsMaintainer: 'false', discussionSubscriberCount: '2', maintainerCount: '2', 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', 'EricBruylant' ], childIds: [], parentIds: [ 'CT_thesis' ], commentIds: [ '4mc' ], questionIds: [], tagIds: [], relatedIds: [], markIds: [], explanations: [], learnMore: [], requirements: [], subjects: [], lenses: [], lensParentId: 'CT_thesis', pathPages: [], learnMoreTaughtMap: {}, learnMoreCoveredMap: {}, learnMoreRequiredMap: {}, editHistory: {}, domainSubmissions: {}, answers: [], answerCount: '0', commentCount: '0', newCommentCount: '0', linkedMarkCount: '0', changeLogs: [ { likeableId: '2790', likeableType: 'changeLog', myLikeValue: '0', likeCount: '1', dislikeCount: '0', likeScore: '1', individualLikes: [], id: '14124', pageId: 'evidence_for_CT_thesis', userId: 'EricBruylant', edit: '5', type: 'newEdit', createdAt: '2016-06-20 19:59:25', auxPageId: '', oldSettingsValue: '', newSettingsValue: 'tidied up links, slight rewording' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '13874', pageId: 'evidence_for_CT_thesis', userId: 'JaimeSevillaMolina', edit: '4', type: 'newEdit', createdAt: '2016-06-18 12:39:27', auxPageId: '', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '13873', pageId: 'evidence_for_CT_thesis', userId: 'JaimeSevillaMolina', edit: '0', type: 'deleteTag', createdAt: '2016-06-18 12:39:23', auxPageId: 'work_in_progress_meta_tag', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '13678', pageId: 'evidence_for_CT_thesis', userId: 'JaimeSevillaMolina', edit: '3', type: 'newEdit', createdAt: '2016-06-17 20:10:44', auxPageId: '', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '13671', pageId: 'evidence_for_CT_thesis', userId: 'JaimeSevillaMolina', edit: '2', type: 'newEdit', createdAt: '2016-06-17 19:20:24', auxPageId: '', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '13668', pageId: 'evidence_for_CT_thesis', userId: 'JaimeSevillaMolina', edit: '1', type: 'newTag', createdAt: '2016-06-17 19:18:23', auxPageId: 'work_in_progress_meta_tag', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '13666', pageId: 'evidence_for_CT_thesis', userId: 'JaimeSevillaMolina', edit: '0', type: 'deleteTag', createdAt: '2016-06-17 19:18:18', auxPageId: 'stub_meta_tag', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '13664', pageId: 'evidence_for_CT_thesis', userId: 'JaimeSevillaMolina', edit: '1', type: 'newTag', createdAt: '2016-06-17 19:18:11', auxPageId: 'stub_meta_tag', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '13662', pageId: 'evidence_for_CT_thesis', userId: 'JaimeSevillaMolina', edit: '1', type: 'newParent', createdAt: '2016-06-17 19:18:00', auxPageId: 'CT_thesis', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '13660', pageId: 'evidence_for_CT_thesis', userId: 'JaimeSevillaMolina', edit: '1', type: 'newEdit', createdAt: '2016-06-17 19:17:43', auxPageId: '', oldSettingsValue: '', newSettingsValue: '' } ], feedSubmissions: [], searchStrings: {}, hasChildren: 'false', hasParents: 'true', redAliases: {}, improvementTagIds: [], nonMetaTagIds: [], todos: [], slowDownMap: 'null', speedUpMap: 'null', arcPageIds: 'null', contentRequests: {} }