The church-turning thesis

xiaoxiao2021-03-06  51

3.1

A Turing machine is a 7-tuple (states, input alphabet, tape alphabet, transition function, start state, accept state, reject state) Call a language is Turing-recognizable if some Turing machine recognize it. Call a language is Turing-decidable If some Turing Machine Decides it.

3.2

Multiple Turing Machines

Non-Deterministic Turing Machines

ENUMERATORS

3.3

Hilbert's 10th problem requires a precise definition of algorithm. Church use the notational system called the l-calculus to defined algorithms and Turing did it with his "machines". There two definitions are shown to be equivalent. This connection between the informal notion of algorithm And The Precise Definition Has Come to Be Called The Church-Turing Thesis.

转载请注明原文地址:https://www.9cbs.com/read-116723.html

New Post(0)