Computability
portes grátis
Computability
Tourlakis, George
Springer Nature Switzerland AG
08/2022
637
Dura
Inglês
9783030832018
15 a 20 dias
1160
Descrição não disponível.
Mathematical Background; a Review.- A Theory of Computability.- Primitive Recursive Functions.- Loop Programs.-The Ackermann Function.- (Un)Computability via Church's Thesis.- Semi-Recursiveness.- Yet another number-theoretic characterisation of P.- Godel's Incompleteness Theorem via the Halting Problem.- The Recursion Theorem.- A Universal (non-PR) Function for PR.- Enumerations of Recursive and Semi-Recursive Sets.- Creative and Productive Sets Completeness.- Relativised Computability.- POSSIBILITY: Complexity of P Functions.- Complexity of PR Functions.- Turing Machines and NP-Completeness.
Este título pertence ao(s) assunto(s) indicados(s). Para ver outros títulos clique no assunto desejado.
recursive functions;formal definability;recursion theorem;diagonalisation;strong reducibility;loop programs;Kleene predicate;Turing reducibility;Register machine;Church's thesis;Goedel incompleteness;Rosser incompleteness;Tarski's theorem;Ackermann function;(Unbounded) Register Machine (URM)
Mathematical Background; a Review.- A Theory of Computability.- Primitive Recursive Functions.- Loop Programs.-The Ackermann Function.- (Un)Computability via Church's Thesis.- Semi-Recursiveness.- Yet another number-theoretic characterisation of P.- Godel's Incompleteness Theorem via the Halting Problem.- The Recursion Theorem.- A Universal (non-PR) Function for PR.- Enumerations of Recursive and Semi-Recursive Sets.- Creative and Productive Sets Completeness.- Relativised Computability.- POSSIBILITY: Complexity of P Functions.- Complexity of PR Functions.- Turing Machines and NP-Completeness.
Este título pertence ao(s) assunto(s) indicados(s). Para ver outros títulos clique no assunto desejado.
