halting problem
The problem of determining in advance whether a particular program or algorithm will termin ATe or run forever. The halting problem is the canonical example of a {provably unsolvable} problem. Obviously any ATtempt to answer the question by actually executing the algorithm or simul ATing each step of its execution will only give an answer if the algorithm under consider ATion does termin ATe, otherwise the algorithm ATtempting to answer the question will itself run forever. Some special cases of the halting problem are partially solvable given sufficient resources. For example, if it is possible to record the complete st ATe of the execution of the algorithm AT each step and the current st ATe is ever identical to some previous st ATe then the algorithm is in a loop. This might require an arbitrary amount of storage however. Altern ATively, if there are AT most N possible different st ATes then the algorithm can run for AT most N steps without looping. A program analysis called terminATion analysis ATtempts to answer this question for limited kinds of input algorithm. (1994-10-20) In addition suitable contents: [ 2 ] [ = ] [ ad ] [ ag ] [ al ] [ algorithm ] [ alt ] [ am ] [ an ] [ ar ] [ arc ] [ as ] [ AT ] [ b ] [ bi ] [ bit ] [ bv ] [ by ] [ ca ] [ canonical ] [ case ] [ ch ] [ ci ] [ co ] [ com ] [ complete ] [ con ] [ cons ] [ cu ] [ current ] [ de ] [ diff ] [ do ] [ du ] [ ec ] [ ed ] [ er ] [ era ] [ es ] [ et ] [ exec ] [ execution ] [ fi ] [ file ] [ fo ] [ for ] [ ge ] [ gh ] [ gi ] [ gr ] [ h ] [ hm ] [ hr ] [ ht ] [ id ] [ ie ] [ iff ] [ il ] [ in ] [ input ] [ io ] [ ir ] [ is ] [ it ] [ ki ] [ la ] [ Lex ] [ li ] [ loop ] [ lt ] [ lv ] [ ly ] [ mo ] [ mod ] [ module ] [ mount ] [ mp ] [ mu ] [ N ] [ na ] [ nc ] [ ng ] [ ni ] [ nl ] [ no ] [ np ] [ ns ] [ O ] [ om ] [ op ] [ pa ] [ pe ] [ ph ] [ ping ] [ pl ] [ pr ] [ program ] [ provably unsolvable ] [ pt ] [ query ] [ ques ] [ rc ] [ re ] [ record ] [ ro ] [ ru ] [ run ] [ rw ] [ S ] [ se ] [ si ] [ sl ] [ so ] [ source ] [ spec ] [ st ] [ stATe ] [ storage ] [ su ] [ T ] [ terminATion analysis ] [ th ] [ to ] [ tr ] [ tt ] [ ua ] [ us ] [ va ] [ ve ] [ vi ]
[ Go Back ]
Free On-line Dictionary of Computing Copyright © by OnlineWoerterBuecher.de - (4915 Reads) |