Wellounded Iterations of ITTMs成立的迭代ittms.pptVIP

Well-founded Iterations of ITTMs(infinite time Turing machines) Robert S. Lubarsky Florida Atlantic University Relations to Wolfram’s work: Good project for an ordinal analysis: just beyond the strongest currently analyzed system Relations to Wolfram’s work: Good project for an ordinal analysis: just beyond the strongest currently analyzed system Iteration and hyper-iteration/feedback Ex: a) Fixed points of inductive definitions: iterated definitions (Pohlers), inductive definitions with feedback – the μ-calculus (M?llerfeld) Iteration and hyper-iteration/feedback Examples: a) Fixed points of inductive definitions: iterated definitions (Pohlers), inductive definitions with feedback – the μ-calculus (M?llerfeld) b) Turing jump: Iteration along any ordinal generated along the way yields the hyperarithmetic sets Iteration and hyper-iteration/feedback Examples: a) Fixed points of inductive definitions : the μ-calculus b) Turing jump : hyperarithmetic sets c) Infinite time Turing machines : ??? Infinite time Turing machine (Hamkins Lewis): a regular Turing machine with limit stages. At a limit stage: machine is in a dedicated state head is on the 0th cell content of a cell is limsup of the previous contents (i.e. 0 if eventually 0, 1 if eventually 1, 1 if cofinally alternating) definitions R ? ω is writable if its characteristic function is on the output tape at the end of a halting computation. An ordinal α is writable if some real coding α (via some standard representation) is writable. λ := sup {α | α is writable} proposition R ? ω is writable iff R ? Lλ . definitions R ? ω is eventually writable if its characteristic function is on the output tape, never to change, of a computation. An ordinal α is eventually writable if some real coding α (via some standard representation) is eventually writable. ζ := sup {α | α is eventually writable} prop R ? ω is eventually writable iff R ? Lζ . definitions R ? ω is accidentally writable if its cha