Tau Meta Language and the notion of Fixed Point

  1. Tau Meta Language and the notion of Fixed Point

---------


Tau Meta Language is very unique in how it works. Each TML program is described as a loop without an arbitrary stopping condition. This is the case because the states of computation are finite. So a TML program merely defines what happens within a single iteration or "instance".


The loop continues until


S ∨ F


A) Two consecutive iterations return the same result (this means success)

i+(1).. i++(1).. S


B) Two non-consequetive iterations return the same result (this means fail)

i+(1).. i++(x).. i+++(1).. F


There can only ever be two possibilities so in essence this is boolean, an either or situation. A represents a Fixed Point which indicates the result is final because the state of the computation has not changed after two consequentive iterations.


To put it more precisely, if a loop ever has a length greater than 1 then it is a fail.


Partial fixed point requires ORDERED structures such as an ordered set. This allows for P-SPACE complexity to be recovered.

0
Comments

Other posts of

@danae


Previous Next

Featured posts


Recent post


TAGS